27 Search Results for "Hrubes, Pavel"

Document
DOI: 10.4230/LIPIcs.STACS.2026.28
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova. Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2026.28,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title =	{{Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.28},
  URN =		{urn:nbn:de:0030-drops-255177},
  doi =		{10.4230/LIPIcs.STACS.2026.28},
  annote =	{Keywords: computational complexity, circuit complexity, lower bounds, conditional lower bounds, monotone circuits, matrix rigidity, tensor rank, arithmetic circuits, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.35
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity

Authors: Pavel Dvořák, Bruno Loff, and Suhail Sherif

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We are interested in what happens when we take a Π₁ combinatorial statement, write its negation as a homogeneous quadratic feasibility problem (HQFP), and relax the problem into a positive semidefinite feasibility problem. This question is particularly interesting owing to the fact that any statement written as a PSD feasibility problem can be proven or disproven using a short proof. We investigate this for one very simple and one very complicated statement. The simple statement we look at is the pigeonhole principle. We prove that the relaxed negation of the PHP remains unsatisfiable and we thus obtain a new "quantum" pigeonhole principle (QPHP) which is a stronger statement than the vanilla PHP. It states that if we take n copies of the same state, and measure each copy using a measurement with only n-1 outcomes (the measurement can be different for different copies), then there will be an outcome j and two copies i₁, i₂ where the resulting states, obtained when the outcome is j for both copies, are not orthogonal. We then look at the statement "the deterministic communication complexity of f is ≤ k", where f could be either a function or a relation. We write this statement in two equivalent ways, using two different HQFPs. By relaxing to PSD feasibility, we increase the set of available protocols, and thus we always get a communication model which is stronger than deterministic communication complexity. An argument from proof complexity shows that any model obtained in this way will solve all Karchmer-Wigderson games efficiently. However, the argument is very indirect and does not give us an explicit protocol that solves the Karchmer-Wigderson games. We then work to find such protocols in the two communication models obtained by relaxing our two formulations. When relaxing the first of the two formulations we obtain a structured variant of the γ₂ norm. This communication model is to subunit γ₂ norm matrices like deterministic protocols are to rectangles, and so we call the protocols in this model γ₂ protocols. We show that log-inverse-discrepancy is a lower-bound for this model. We then show how to compute equality (deterministically) using O(1) bits of γ₂-communication, which implies that KW games are easy in the model. When relaxing the second of the two formulations we obtain what we call quantum lab protocols. This model happens to have a functional description, wherein Alice and Bob communicate solely via the outcomes of binary measurements of a shared quantum state (whose initial state is independent of the inputs). They are required to give the correct output with zero error probability. We use our QPHP to prove a lower-bound of n against two-round quantum lab protocols for equality. However we also show that any Boolean function f can be computed in three rounds and four measurements.
Cite as

Pavel Dvořák, Bruno Loff, and Suhail Sherif. A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2026.35,
  author =	{Dvo\v{r}\'{a}k, Pavel and Loff, Bruno and Sherif, Suhail},
  title =	{{A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.35},
  URN =		{urn:nbn:de:0030-drops-255243},
  doi =		{10.4230/LIPIcs.STACS.2026.35},
  annote =	{Keywords: Proofs, Semidefinite Programs, Quantum Pigeonhole Principle, Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.113
Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP

Authors: Benjamin Rossman and Davidson Zhu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The sum-of-squares (SoS) complexity of a d-multiquadratic polynomial f (quadratic in each of d blocks of n variables) is the minimum s such that f = ∑_{i = 1}^s g_i² with each g_i d-multilinear. In the case d = 2, Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011] showed that an n^{1+Ω(1)} lower bound on the SoS complexity of explicit biquadratic polynomials implies an exponential lower bound for non-commutative arithmetic circuits. In this paper, we establish an analogous connection between general multiquadratic sum-of-squares and commutative arithmetic formulas. Specifically, we show that an n^{d-o(log d)} lower bound on the SoS complexity of explicit d-multiquadratic polynomials, for any d = d(n) with ω(1) ≤ d(n) ≤ O((log n)/(log log n)), would separate the algebraic complexity classes VNC¹ and VNP.
Cite as

Benjamin Rossman and Davidson Zhu. Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 113:1-113:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rossman_et_al:LIPIcs.ITCS.2026.113,
  author =	{Rossman, Benjamin and Zhu, Davidson},
  title =	{{Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{113:1--113:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.113},
  URN =		{urn:nbn:de:0030-drops-254006},
  doi =		{10.4230/LIPIcs.ITCS.2026.113},
  annote =	{Keywords: sum-of-squares, arithmetic formulas}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.115
Lower Bounds for Noncommutative Circuits with Low Syntactic Degree

Authors: Pratik Shastri

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Proving lower bounds on the size of noncommutative arithmetic circuits is an important problem in arithmetic circuit complexity. For explicit n variate polynomials of degree Θ(n), the best known general bound is Ω(n log n) [Strassen, 1973; Walter Baur and Volker Strassen, 1983]. Recent work of Chatterjee and Hrubeš [Chatterjee and Hrubeš, 2023] has provided stronger (Ω(n²)) bounds for the restricted class of homogeneous circuits. The present paper extends these results to a broader class of circuits by using syntactic degree as a complexity measure. The syntactic degree of a circuit is a well known parameter which measures the extent to which high degree computation is used in the circuit. A homogeneous circuit computing a degree d polynomial can be assumed, without loss of generality, to have syntactic degree exactly equal to d [Fournier et al., 2024]. We generalize this by considering circuits that are not necessarily homogeneous but have low syntactic degree. Specifically, for an explicit n variate, degree n polynomial f we show that any circuit with syntactic degree O(n) computing f must have size Ω(n^{1+c}) for some constant c > 0. We also show that any circuit with syntactic degree o(nlog n) computing the same f must have size ω(nlog n). We further analyze the circuit size required to compute f based on the number of distinct syntactic degrees appearing in the circuit. Our analysis yields an ω(nlog n) size lower bound for all but a narrow parameter regime where an improved bound is not obtained. Finally, we observe that low syntactic degree circuits are more powerful than homogeneous circuits in a fine grained sense: there exists an n variate, degree Θ(n) polynomial that has a circuit of size O(nlog ²n) and syntactic degree O(n) but any homogeneous circuit computing it requires size Ω(n²).
Cite as

Pratik Shastri. Lower Bounds for Noncommutative Circuits with Low Syntactic Degree. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 115:1-115:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shastri:LIPIcs.ITCS.2026.115,
  author =	{Shastri, Pratik},
  title =	{{Lower Bounds for Noncommutative Circuits with Low Syntactic Degree}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{115:1--115:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.115},
  URN =		{urn:nbn:de:0030-drops-254028},
  doi =		{10.4230/LIPIcs.ITCS.2026.115},
  annote =	{Keywords: Noncommutative Circuits, Lower Bounds, Circuit Complexity, Algebraic Complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.47
The Algebraic Cost of a Boolean Sum

Authors: Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, and Amir Yehudayoff

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the "cost of a boolean sum", while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity.
Cite as

Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, and Amir Yehudayoff. The Algebraic Cost of a Boolean Sum. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{orzel_et_al:LIPIcs.FSTTCS.2025.47,
  author =	{Orzel, Ian and Srinivasan, Srikanth and Tavenas, S\'{e}bastien and Yehudayoff, Amir},
  title =	{{The Algebraic Cost of a Boolean Sum}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.47},
  URN =		{urn:nbn:de:0030-drops-251271},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.47},
  annote =	{Keywords: Algebraic Complexity, Computational Complexity, Permanent, Determinant}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.56
Efficient Polynomial Identity Testing over Nonassociative Algebras

Authors: Partha Mukhopadhyay, C. Ramya, and Pratik Shastri

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrubeš, Yehudayoff, and Wigderson [Pavel Hrubes et al., 2010] and Fijalkow, Lagarde, Ohlmann, and Serre [Fijalkow et al., 2021] from the identity testing perspective. Our main results are the following: - We construct nonassociative algebras (both commutative and noncommutative) which have no low degree identities. As a result, we obtain the first Amitsur-Levitzki type theorems [A. S. Amitsur and J. Levitzki, 1950] over nonassociative polynomial algebras. As a direct consequence, we obtain randomized polynomial-time black-box PIT algorithms for nonassociative polynomials which allow evaluation over such algebras. - On the derandomization side, we give a deterministic polynomial-time identity testing algorithm for nonassociative polynomials given by arithmetic circuits in the white-box setting. Previously, such an algorithm was known with the additional restriction of noncommutativity [Vikraman Arvind et al., 2017]. - In the black-box setting, we construct a hitting set of quasipolynomial-size for nonassociative polynomials computed by arithmetic circuits of small depth. Understanding the black-box complexity of identity testing, even in the randomized setting, was open prior to our work.
Cite as

Partha Mukhopadhyay, C. Ramya, and Pratik Shastri. Efficient Polynomial Identity Testing over Nonassociative Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 56:1-56:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukhopadhyay_et_al:LIPIcs.APPROX/RANDOM.2025.56,
  author =	{Mukhopadhyay, Partha and C. Ramya and Shastri, Pratik},
  title =	{{Efficient Polynomial Identity Testing over Nonassociative Algebras}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{56:1--56:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.56},
  URN =		{urn:nbn:de:0030-drops-244224},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.56},
  annote =	{Keywords: Polynomial identity testing, nonassociative algebra, arithmetic circuits, black-box algorithms, white-box algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.64
Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication

Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We show that for a randomly sampled unsatisfiable O(log n)-CNF over n variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in n.
Cite as

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan. Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riazanov_et_al:LIPIcs.APPROX/RANDOM.2025.64,
  author =	{Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry and Yuan, Weiqiang},
  title =	{{Searching for Falsified Clause in Random (log\{n\})-CNFs Is Hard for Randomized Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.64},
  URN =		{urn:nbn:de:0030-drops-244306},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.64},
  annote =	{Keywords: communication complexity, proof complexity, random CNF}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.19
Monotone Bounded-Depth Complexity of Homomorphism Polynomials

Authors: C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.
Cite as

C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi. Monotone Bounded-Depth Complexity of Homomorphism Polynomials. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargav_et_al:LIPIcs.MFCS.2025.19,
  author =	{Bhargav, C.S. and Chen, Shiteng and Curticapean, Radu and Dwivedi, Prateek},
  title =	{{Monotone Bounded-Depth Complexity of Homomorphism Polynomials}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.19},
  URN =		{urn:nbn:de:0030-drops-241269},
  doi =		{10.4230/LIPIcs.MFCS.2025.19},
  annote =	{Keywords: algebraic complexity, homomorphisms, monotone circuit complexity, bounded-depth circuits, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.32
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion

Authors: Anastasia Sofronova and Dmitry Sokolov

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Random Δ-CNF formulas are one of the few candidates that are expected to be hard for proof systems and SAT algotirhms. Assume we sample m clauses over n variables. Here, the main complexity parameter is clause density, χ := m/n. For a fixed Δ, there exists a satisfiability threshold c_Δ such that for χ > c_Δ a formula is unsatisfiable with high probability. and for χ < c_Δ it is satisfiable with high probability. Near satisfiability threshold, there are various lower bounds for algorithms and proof systems [Eli Ben-Sasson, 2001; Eli Ben-Sasson and Russell Impagliazzo, 1999; Michael Alekhnovich and Alexander A. Razborov, 2003; Dima Grigoriev, 2001; Grant Schoenebeck, 2008; Pavel Hrubes and Pavel Pudlák, 2017; Noah Fleming et al., 2017; Dmitry Sokolov, 2024], and for high-density regimes, there exist upper bounds [Uriel Feige et al., 2006; Sebastian Müller and Iddo Tzameret, 2014; Jackson Abascal et al., 2021; Venkatesan Guruswami et al., 2022]. One of the frontiers in the direction of proving lower bounds on these formulas is the k-DNF Resolution proof system (aka Res(k)). There are several known results for k = 𝒪(√{log n}/{log log n}}) [Nathan Segerlind et al., 2004; Michael Alekhnovich, 2011], that are applicable only for density regime near the threshold. In this paper, we show the first Res(k) lower bound that is applicable in higher-density regimes. Our results work for slightly larger k = 𝒪(√{log n}).
Cite as

Anastasia Sofronova and Dmitry Sokolov. A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 32:1-32:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sofronova_et_al:LIPIcs.CCC.2025.32,
  author =	{Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{32:1--32:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.32},
  URN =		{urn:nbn:de:0030-drops-237269},
  doi =		{10.4230/LIPIcs.CCC.2025.32},
  annote =	{Keywords: proof complexity, random CNFs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.36
Lifting with Colourful Sunflowers

Authors: Susanna F. de Rezende and Marc Vinyals

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P.
Cite as

Susanna F. de Rezende and Marc Vinyals. Lifting with Colourful Sunflowers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2025.36,
  author =	{de Rezende, Susanna F. and Vinyals, Marc},
  title =	{{Lifting with Colourful Sunflowers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.36},
  URN =		{urn:nbn:de:0030-drops-237303},
  doi =		{10.4230/LIPIcs.CCC.2025.36},
  annote =	{Keywords: lifting, sunflower, clique, colouring, monotone circuit, cutting planes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.21
Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles

Authors: Paul Beame and Michael Whitmeyer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We prove several results concerning the communication complexity of a collision-finding problem, each of which has applications to the complexity of cutting-plane proofs, which make inferences based on integer linear inequalities. In particular, we prove an Ω(n^{1-1/k} log k /2^k) lower bound on the k-party number-in-hand communication complexity of collision-finding. This implies a 2^{n^{1-o(1)}} lower bound on the size of tree-like cutting-planes refutations of the bit pigeonhole principle CNFs, which are compact and natural propositional encodings of the negation of the pigeonhole principle, improving on the best previous lower bound of 2^{Ω(√n)}. Using the method of density-restoring partitions, we also extend that previous lower bound to the full range of pigeonhole parameters. Finally, using a refinement of a bottleneck-counting framework of Haken and Cook and Sokolov for DAG-like communication protocols, we give a 2^{Ω(n^{1/4})} lower bound on the size of fully general (not necessarily tree-like) cutting planes refutations of the same bit pigeonhole principle formulas, improving on the best previous lower bound of 2^{Ω(n^{1/8})}.
Cite as

Paul Beame and Michael Whitmeyer. Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beame_et_al:LIPIcs.ICALP.2025.21,
  author =	{Beame, Paul and Whitmeyer, Michael},
  title =	{{Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.21},
  URN =		{urn:nbn:de:0030-drops-233982},
  doi =		{10.4230/LIPIcs.ICALP.2025.21},
  annote =	{Keywords: Proof Complexity, Communication Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.11
A Near-Optimal Polynomial Distance Lemma over Boolean Slices

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field 𝔽, are non-zero over any "grid" (points of the form Sⁿ for finite subset S ⊆ 𝔽) with probability at least max{|S|^{-d/(|S|-1)},1-d/|S|} over the choice of random point from the grid. In particular, over the Boolean cube (S = {0,1} ⊆ 𝔽), the lemma asserts non-zero polynomials are non-zero with probability at least 2^{-d}. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly k. We show that non-zero polynomials on the slice are non-zero with probability (t/n)^{d}(1 - o_{n}(1)) where t = min{k,n-k} for every d ≤ k ≤ (n-d). As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight upto the error term as evidenced by multilinear monomials of degree d, and it is also the case that some corrective term is necessary. A particularly interesting case is the "balanced slice" (k = n/2) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025), who established a sub-optimal bound of approximately ((k/n)⋅ (1-(k/n)))^d using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. A Near-Optimal Polynomial Distance Lemma over Boolean Slices. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.ICALP.2025.11,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{A Near-Optimal Polynomial Distance Lemma over Boolean Slices}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.11},
  URN =		{urn:nbn:de:0030-drops-233881},
  doi =		{10.4230/LIPIcs.ICALP.2025.11},
  annote =	{Keywords: Low-degree polynomials, Boolean slices, Schwartz-Zippel Lemma}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.26
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function

Authors: Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of (3 - o(1))log n established by Håstad over 25 years ago. The Karchmer-Raz-Wigderson (KRW) conjecture offers a promising approach to advance these bounds and separate P from NC¹. It suggests that the depth complexity of a function composition f ⋄ g approximates the sum of the depth complexities of f and g. The Karchmer-Wigderson (KW) relation framework translates formula depth into communication complexity, restating the KRW conjecture as CC(KW_f ⋄ KW_g) ≈ CC(KW_f) + CC(KW_g). Prior work has confirmed the conjecture under various relaxations, often replacing one or both KW relations with the universal relation or constraining the communication game through strong composition. In this paper, we examine the strong composition KW_XOR ⊛ KW_f of the parity function and a random Boolean function f. We prove that with probability 1-o(1), any protocol solving this composition requires at least n^{3 - o(1)} leaves. This result establishes a depth lower bound of (3 - o(1))log n, matching Håstad’s bound, but is applicable to a broader class of inner functions, even when the outer function is simple. Though bounds for the strong composition do not translate directly to formula depth bounds, they usually help to analyze the standard composition (of the corresponding two functions) which is directly related to formula depth. Our proof utilizes formal complexity measures. First, we apply Khrapchenko’s method to show that numerous instances of f remain unsolved after several communication steps. Subsequently, we transition to a different formal complexity measure to demonstrate that the remaining communication problem is at least as hard as KW_OR ⊛ KW_f. This hybrid approach not only achieves the desired lower bound, but also introduces a novel technique for analyzing formula depth, potentially informing future research in complexity theory.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin. Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2025.26,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan},
  title =	{{Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.26},
  URN =		{urn:nbn:de:0030-drops-228513},
  doi =		{10.4230/LIPIcs.STACS.2025.26},
  annote =	{Keywords: complexity, formula complexity, lower bounds, Boolean functions, depth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.53
On Read-k Projections of the Determinant

Authors: Pavel Hrubeš and Pushkar S. Joglekar

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider read-k determinantal representations of polynomials and prove some non-expressibility results. A square matrix M whose entries are variables or field elements will be called read-k, if every variable occurs at most k times in M. It will be called a determinantal representation of a polynomial f if f = det(M). We show that - the n × n permanent polynomial does not have a read-k determinantal representation for k ∈ o(√n/log n) (over a field of characteristic different from two). We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for k ∈ o(√n/log n) for an explicit n-variate multilinear polynomial (as opposed to the permanent which is n²-variate).
Cite as

Pavel Hrubeš and Pushkar S. Joglekar. On Read-k Projections of the Determinant. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 53:1-53:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hrubes_et_al:LIPIcs.STACS.2025.53,
  author =	{Hrube\v{s}, Pavel and Joglekar, Pushkar S.},
  title =	{{On Read-k Projections of the Determinant}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{53:1--53:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.53},
  URN =		{urn:nbn:de:0030-drops-228785},
  doi =		{10.4230/LIPIcs.STACS.2025.53},
  annote =	{Keywords: determinant, permanent, projection of determinant, VNP completeness of permanent}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.12
A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas

Authors: Pavel Hrubeš

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
For every n, we construct a sum-of-squares identity (∑_{i=1}^n x_i²) (∑_{j=1}^n y_j²) = ∑_{k=1}^s f_k², where f_k are bilinear forms with complex coefficients and s = O(n^1.62). Previously, such a construction was known with s = O(n²/log n). The same bound holds over any field of positive characteristic.
Cite as

Pavel Hrubeš. A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hrubes:LIPIcs.CCC.2024.12,
  author =	{Hrube\v{s}, Pavel},
  title =	{{A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{12:1--12:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.12},
  URN =		{urn:nbn:de:0030-drops-204082},
  doi =		{10.4230/LIPIcs.CCC.2024.12},
  annote =	{Keywords: Sum-of-squares composition formulas, Hurwitz’s problem, non-commutative arithmetic circuit}
}
  • Refine by Type
  • 27 Document/PDF
  • 14 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 10 2025
  • 2 2024
  • 1 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 7 Hrubeš, Pavel
  • 4 Mukhopadhyay, Partha
  • 4 Yehudayoff, Amir
  • 2 Chattopadhyay, Arkadev
  • 2 Chukhin, Nikolai
  • Show More...

  • Refine by Series/Journal
  • 27 LIPIcs

  • Refine by Classification
  • 11 Theory of computation → Algebraic complexity theory
  • 6 Theory of computation → Circuit complexity
  • 4 Theory of computation → Proof complexity
  • 3 Theory of computation
  • 3 Theory of computation → Communication complexity
  • Show More...

  • Refine by Keyword
  • 4 Communication Complexity
  • 4 communication complexity
  • 4 proof complexity
  • 3 Algebraic Complexity
  • 3 Lower Bounds
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact