24 Search Results for "Volk, Ben Lee"

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.ITCS.2026.9
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Authors: Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

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

Abstract
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.
Cite as

Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andrews_et_al:LIPIcs.ITCS.2026.9,
  author =	{Andrews, Robert and Armand, Jules and Dwivedi, Prateek and Hansen, Magnus Rahbek Dalgaard and Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On Closure Properties of Read-Once Oblivious Algebraic Branching Programs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{9:1--9:21},
  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.9},
  URN =		{urn:nbn:de:0030-drops-252964},
  doi =		{10.4230/LIPIcs.ITCS.2026.9},
  annote =	{Keywords: Factoring, Closure Properties, Sparsity Bounds, Symmetric Polynomials, roABP, Expander Graphs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.43
Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio

Authors: Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang

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

Abstract
In this paper, we show that random Gabidulin codes of block length n and rate R achieve the (average-radius) list decoding capacity of radius 1-R-ε in the rank metric with an order-optimal column-to-row ratio of O(ε). This extends the recent work of Guo, Xing, Yuan, and Zhang (FOCS 2024), improving their column-to-row ratio from O(ε/n) to O(ε). For completeness, we also establish a matching lower bound on the column-to-row ratio for capacity-achieving Gabidulin codes in the rank metric. Our proof techniques build on the work of Guo and Zhang (FOCS 2023), who showed that randomly punctured Reed-Solomon codes over fields of quadratic size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020) in the Hamming metric. The proof of our lower bound follows the method of Alrabiah, Guruswami, and Li (SODA 2024) for codes in the Hamming metric.
Cite as

Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang. Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2025.43,
  author =	{Guo, Zeyu and Xing, Chaoping and Yuan, Chen and Zhang, Zihan},
  title =	{{Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{43:1--43:20},
  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.43},
  URN =		{urn:nbn:de:0030-drops-244095},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.43},
  annote =	{Keywords: coding theory, error-correcting codes, Gabidulin codes, rank-metric codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.66
Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

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

Abstract
Let f and g be Boolean functions over a finite Abelian group 𝒢, where g is fully known and f is accessible via queries; that is, given any x ∈ 𝒢, we can obtain the value f(x). We study the problem of tolerant isomorphism testing: given parameters ε ≥ 0 and τ > 0, the goal is to determine, using as few queries as possible, whether there exists an automorphism σ of 𝒢 such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for every automorphism σ, the distance is at least ε + τ. We design an efficient tolerant property testing algorithm for this problem over finite Abelian groups with constant exponent. The exponent of a finite group refers to the largest order of any element in the group. The query complexity of our algorithm is polynomial in s and 1/τ, where s bounds the spectral norm of the function g, and τ is the tolerance parameter. In addition, we present an improved algorithm in the case where g is Fourier sparse, meaning that its Fourier expansion contains only a small number of nonzero coefficients. Our approach draws on key ideas from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner product defined over finite Abelian groups. We believe that these techniques will be useful more broadly in the design of property testing algorithms.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Testing Isomorphism of Boolean Functions over Finite Abelian Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.APPROX/RANDOM.2025.66,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Testing Isomorphism of Boolean Functions over Finite Abelian Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{66:1--66: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.66},
  URN =		{urn:nbn:de:0030-drops-244328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  annote =	{Keywords: Analysis of Boolean functions, Abelian groups, Automorphism group, Function isomorphism, Spectral norm}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.1
List Decoding Quotient Reed-Muller Codes

Authors: Omri Gotlib, Tali Kaufman, and Shachar Lovett

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

Abstract
Reed-Muller codes consist of evaluations of n-variate polynomials over a finite field 𝔽 with degree at most d. Much like every linear code, Reed-Muller codes can be characterized by constraints, where a codeword is valid if and only if it satisfies all degree-d constraints. For a subset X̃ ⊆ 𝔽ⁿ, we introduce the notion of X̃-quotient Reed-Muller code. A function F:X̃ → 𝔽 is a valid codeword in the quotient code if it satisfies all the constraints of degree-d polynomials lying in X̃. This gives rise to a novel phenomenon: a quotient codeword may have many extensions to original codewords. This weakens the connection between original codewords and quotient codewords which introduces a richer range of behaviors along with substantial new challenges. Our goal is to answer the following question: what properties of X̃ will imply that the quotient code inherits its distance and list-decoding radius from the original code? We address this question using techniques developed by Bhowmick and Lovett [Abhishek Bhowmick and Shachar Lovett, 2014], identifying key properties of 𝔽ⁿ used in their proof and extending them to general subsets X̃ ⊆ 𝔽ⁿ. By introducing a new tool, we overcome the novel challenge in analyzing the quotient code that arises from the weak connection between original and quotient codewords. This enables us to apply known results from additive combinatorics and algebraic geometry [David Kazhdan and Tamar Ziegler, 2018; David Kazhdan and Tamar Ziegler, 2019; Amichai Lampert and Tamar Ziegler, 2021] to show that when X̃ is a high rank variety, X̃-quotient Reed-Muller codes inherit the distance and list-decoding parameters from the original Reed-Muller codes.
Cite as

Omri Gotlib, Tali Kaufman, and Shachar Lovett. List Decoding Quotient Reed-Muller Codes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 1:1-1:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.CCC.2025.1,
  author =	{Gotlib, Omri and Kaufman, Tali and Lovett, Shachar},
  title =	{{List Decoding Quotient Reed-Muller Codes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{1:1--1:44},
  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.1},
  URN =		{urn:nbn:de:0030-drops-236957},
  doi =		{10.4230/LIPIcs.CCC.2025.1},
  annote =	{Keywords: Reed-Muller Codes, Quotient Code, Quotient Reed-Muller Code, List Decoding, High Rank Variety, High-Order Fourier Analysis, Error-Correcting Codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.21
Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3

Authors: Shubhangi Saraf and Devansh Shringi

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

Abstract
In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 (ΣΠΣ(3) circuits) over the fields ℝ and C. Concretely, we show that given blackbox access to an n-variate polynomial f computed by a ΣΠΣ(3) circuit of size s, there is a randomized algorithm that runs in time quasi-poly(n,s) and outputs a generalized ΣΠΣ(3) circuit computing f. The size s includes the bit complexity of coefficients appearing in the circuit. Depth 3 circuits of constant fan-in (ΣΠΣ(k) circuits) and closely related models have been extensively studied in the context of polynomial identity testing (PIT). The study of PIT for these models led to an understanding of the structure of identically zero ΣΠΣ(3) circuits and ΣΠΣ(k) circuits using some very elegant connections to discrete geometry, specifically the Sylvester-Gallai Theorem, and colorful and high dimensional variants of them. Despite a lot of progress on PIT for ΣΠΣ(k) circuits and more recently on PIT for depth 4 circuits of bounded top and bottom fan-in, reconstruction algorithms for ΣΠΣ(k) circuits has proven to be extremely challenging. In this paper, we build upon the structural results for identically zero ΣΠΣ(3) circuits that bound their rank, and prove stronger structural properties of ΣΠΣ(3) circuits (again using connections to discrete geometry). One such result is a bound on the number of codimension 3 subspaces on which a polynomial computed by an ΣΠΣ(3) circuit can vanish on. Armed with the new structural results, we provide the first reconstruction algorithms for ΣΠΣ(3) circuits over ℝ and C. Our work extends the work of [Sinha, CCC 2016] who provided a reconstruction algorithm for ΣΠΣ(2) circuits over ℝ and C as well as the works of [Shpilka, STOC 2007] who provided a reconstruction algorithms for ΣΠΣ(2) circuits in the setting of small finite fields, and [Karnin-Shpilka, CCC 2009] who provided reconstruction algorithms for ΣΠΣ(k) circuits in the setting of small finite fields.
Cite as

Shubhangi Saraf and Devansh Shringi. Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saraf_et_al:LIPIcs.CCC.2025.21,
  author =	{Saraf, Shubhangi and Shringi, Devansh},
  title =	{{Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{21:1--21:22},
  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.21},
  URN =		{urn:nbn:de:0030-drops-237151},
  doi =		{10.4230/LIPIcs.CCC.2025.21},
  annote =	{Keywords: arithmetic circuits, learning, reconstruction}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.16
Direct Sums for Parity Decision Trees

Authors: Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan

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

Abstract
Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.
Cite as

Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan. Direct Sums for Parity Decision Trees. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{besselman_et_al:LIPIcs.CCC.2025.16,
  author =	{Besselman, Tyler and G\"{o}\"{o}s, Mika and Guo, Siyao and Maystre, Gilbert and Yuan, Weiqiang},
  title =	{{Direct Sums for Parity Decision Trees}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{16:1--16:38},
  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.16},
  URN =		{urn:nbn:de:0030-drops-237105},
  doi =		{10.4230/LIPIcs.CCC.2025.16},
  annote =	{Keywords: direct sum, parity decision trees, query complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.15
Algebraic Pseudorandomness in VNC⁰

Authors: Robert Andrews

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

Abstract
We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.
Cite as

Robert Andrews. Algebraic Pseudorandomness in VNC⁰. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andrews:LIPIcs.CCC.2025.15,
  author =	{Andrews, Robert},
  title =	{{Algebraic Pseudorandomness in VNC⁰}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{15:1--15:15},
  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.15},
  URN =		{urn:nbn:de:0030-drops-237092},
  doi =		{10.4230/LIPIcs.CCC.2025.15},
  annote =	{Keywords: Polynomial identity testing, Algebraic circuits, Ideal Proof System}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.28
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

Authors: Vishwas Bhargava and Devansh Shringi

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

Abstract
We present a deterministic 2^{k^{𝒪(1)}} poly(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over ℝ and ℂ. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{𝒪(k)}}} poly(n,d) time and the deterministic n^k^k time algorithms of Bhargava, Saraf, and Volkovich (STOC '21). Our work resolves an open question asked by Peleg, Shpilka, and Volk (ITCS '24) on whether a deterministic Fixed Parameter Tractable (FPT) algorithm exists for worst-case tensor decomposition. We also make substantial progress on the fundamental problem of how the tractability of tensor decomposition varies as the tensor rank increases. Our result implies that we can achieve deterministic polynomial-time decomposition as long as the rank of the tensor is at most (log n)^{1/C}, where C is some fixed constant independent of n and d. Further, we note that there cannot exist a polynomial-time algorithm for k = ω(log n) unless ETH fails. Our algorithm works for all fields; however, the time complexity worsens to 2^{k^{k^{𝒪(1)}}} and requires randomization for finite fields of large characteristics. Both conditions are provably necessary unless there are improvements in the state of the art for system solving over the corresponding fields. Our approach achieves this by designing a proper learning (reconstruction) algorithm for set-multilinear depth-3 arithmetic circuits. On a technical note, we design a "partial" clustering algorithm for set-multilinear depth-3 arithmetic circuits that lets us isolate a cluster from any set-multilinear depth-3 circuit while preserving the structure of the circuit.
Cite as

Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.ICALP.2025.28,
  author =	{Bhargava, Vishwas and Shringi, Devansh},
  title =	{{Faster \& Deterministic FPT Algorithm for Worst-Case Tensor Decomposition}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{28:1--28: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.28},
  URN =		{urn:nbn:de:0030-drops-234052},
  doi =		{10.4230/LIPIcs.ICALP.2025.28},
  annote =	{Keywords: Algebraic circuits, Deterministic algorithms, FPT algorithm, Learning circuits, Reconstruction, Tensor Decomposition, Tensor Rank}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.37
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications

Authors: Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We present a simple method based on a variant of Hölder’s inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier L₁-norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini and Shirley (CCC 2023). As immediate consequences, we obtain the following results. - We give an exponential separation between the logarithm of the randomized and the deterministic parity decision tree size. This is in sharp contrast with the standard binary decision tree setting where the logarithms of randomized and deterministic decision tree size are essentially polynomially related, as shown recently by Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (STOC 2023). - We give an exponential separation between the approximate and the exact spectral norm for Boolean functions. - We give an exponential separation for XOR functions between the deterministic communication complexity with oracle access to Equality function (D^EQ) and randomized communication complexity. Previously, such a separation was known for general Boolean matrices by Chattopadhyay, Lovett, and Vinyals (CCC 2019) using the Integer Inner Product (IIP) function. - Finally, our method gives an elementary and short proof for the mentioned exponential D^EQ lower bound of Chattopadhyay, Lovett, and Vinyals for Integer Inner Product (IIP).
Cite as

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cheung_et_al:LIPIcs.ITCS.2025.37,
  author =	{Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Nikolov, Aleksandar and Pitassi, Toniann and Shirley, Morgan},
  title =	{{A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-226654},
  doi =		{10.4230/LIPIcs.ITCS.2025.37},
  annote =	{Keywords: Boolean function complexity, parity decision trees, randomized communication complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.44
Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields

Authors: Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk

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

Abstract
We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field 𝔽_q. The seed length of our generators is O(d log n + log q), over fields of size exponential in d and characteristic at least d(d-1)+1. Previous constructions such as Bogdanov’s (STOC 2005) and Derksen and Viola’s (FOCS 2022) had either suboptimal seed length or required the field size to depend on n. Our approach follows Bogdanov’s paradigm while incorporating techniques from Lecerf’s factorization algorithm (J. Symb. Comput. 2007) and insights from the construction of Derksen and Viola regarding the role of indecomposability of polynomials.
Cite as

Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dwivedi_et_al:LIPIcs.APPROX/RANDOM.2024.44,
  author =	{Dwivedi, Ashish and Guo, Zeyu and Volk, Ben Lee},
  title =	{{Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.44},
  URN =		{urn:nbn:de:0030-drops-210370},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.44},
  annote =	{Keywords: Pseudorandom Generators, Low Degree Polynomials}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.27
Determinants vs. Algebraic Branching Programs

Authors: Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We show that for every homogeneous polynomial of degree d, if it has determinantal complexity at most s, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O(d⁵s). Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s-1 and the size is at most O(ds). Thus, for constant degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree [Mrinal Kumar, 2019; Prerona Chatterjee et al., 2022], and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor [Mrinal Kumar and Ben Lee Volk, 2022]. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent [Meena Mahajan and V. Vinay, 1997], the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant degree polynomials.
Cite as

Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk. Determinants vs. Algebraic Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ITCS.2024.27,
  author =	{Chatterjee, Abhranil and Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Determinants vs. Algebraic Branching Programs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27},
  URN =		{urn:nbn:de:0030-drops-195550},
  doi =		{10.4230/LIPIcs.ITCS.2024.27},
  annote =	{Keywords: Determinant, Algebraic Branching Program, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.87
Tensor Reconstruction Beyond Constant Rank

Authors: Shir Peleg, Amir Shpilka, and Ben Lee Volk

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results: 1) A deterministic algorithm that reconstructs polynomials computed by Σ^{[k]}⋀^{[d]}Σ circuits in time poly(n,d,c) ⋅ poly(k)^{k^{k^{10}}}, 2) A randomized algorithm that reconstructs polynomials computed by multilinear Σ^{[k]}∏^{[d]}Σ circuits in time poly(n,d,c) ⋅ k^{k^{k^{k^{O(k)}}}}, 3) A randomized algorithm that reconstructs polynomials computed by set-multilinear Σ^{[k]}∏^{[d]}Σ circuits in time poly(n,d,c) ⋅ k^{k^{k^{k^{O(k)}}}}, where c = log q if 𝔽 = 𝔽_q is a finite field, and c equals the maximum bit complexity of any coefficient of f if 𝔽 is infinite. Prior to our work, polynomial time algorithms for the case when the rank, k, is constant, were given by Bhargava, Saraf and Volkovich [Vishwas Bhargava et al., 2021]. Another contribution of this work is correcting an error from a paper of Karnin and Shpilka [Zohar Shay Karnin and Amir Shpilka, 2009] (with some loss in parameters) that also affected Theorem 1.6 of [Vishwas Bhargava et al., 2021]. Consequently, the results of [Zohar Shay Karnin and Amir Shpilka, 2009; Vishwas Bhargava et al., 2021] continue to hold, with a slightly worse setting of parameters. For fixing the error we systematically study the relation between syntactic and semantic notions of rank of Σ Π Σ circuits, and the corresponding partitions of such circuits. We obtain our improved running time by introducing a technique for learning rank preserving coordinate-subspaces. Both [Zohar Shay Karnin and Amir Shpilka, 2009] and [Vishwas Bhargava et al., 2021] tried all choices of finding the "correct" coordinates, which, due to the size of the set, led to having a fast growing function of k at the exponent of n. We manage to find these spaces in time that is still growing fast with k, yet it is only a fixed polynomial in n.
Cite as

Shir Peleg, Amir Shpilka, and Ben Lee Volk. Tensor Reconstruction Beyond Constant Rank. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{peleg_et_al:LIPIcs.ITCS.2024.87,
  author =	{Peleg, Shir and Shpilka, Amir and Volk, Ben Lee},
  title =	{{Tensor Reconstruction Beyond Constant Rank}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{87:1--87:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.87},
  URN =		{urn:nbn:de:0030-drops-196157},
  doi =		{10.4230/LIPIcs.ITCS.2024.87},
  annote =	{Keywords: Algebraic circuits, reconstruction, tensor decomposition, tensor rank}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.23
Playing Guess Who with Your Kids

Authors: Ami Paz and Liat Peterfreund

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Guess who is a two-player search game in which each player chooses a character from a deck of 24 cards, and has to infer the other player’s character by asking yes-no questions. A simple binary search strategy allows the starting player find the opponent’s character by asking 5 questions only, when the opponent is honest. Real-life observations show that in more realistic scenarios, the game is played against adversaries that do not strictly follow the rules, e.g., kids. Such players might decide to answer all questions at once, answer only part of the questions as they do not know the answers to all, and even lie occasionally. We devise strategies for such scenarios using techniques from error-correcting and erasure codes. This connects to a recent line of work on search problems on graphs and trees with unreliable auxiliary information, and could be of independent interest.
Cite as

Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{paz_et_al:LIPIcs.FUN.2022.23,
  author =	{Paz, Ami and Peterfreund, Liat},
  title =	{{Playing Guess Who with Your Kids}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{23:1--23:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.23},
  URN =		{urn:nbn:de:0030-drops-159935},
  doi =		{10.4230/LIPIcs.FUN.2022.23},
  annote =	{Keywords: Guess Who?, Binary Search, Error Correcting Codes, Erasure Codes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.44
If VNP Is Hard, Then so Are Equations for It

Authors: Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee, Kumar, Ramya, Saptharishi and Tengse (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.
Cite as

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44,
  author =	{Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{If VNP Is Hard, Then so Are Equations for It}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44},
  URN =		{urn:nbn:de:0030-drops-158547},
  doi =		{10.4230/LIPIcs.STACS.2022.44},
  annote =	{Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs}
}
  • Refine by Type
  • 24 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 8 2025
  • 3 2024
  • 3 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 11 Volk, Ben Lee
  • 8 Kumar, Mrinal
  • 4 Shpilka, Amir
  • 3 Saptharishi, Ramprasad
  • 2 Andrews, Robert
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs

  • Refine by Classification
  • 12 Theory of computation → Algebraic complexity theory
  • 7 Theory of computation → Circuit complexity
  • 4 Theory of computation → Pseudorandomness and derandomization
  • 2 Mathematics of computing → Coding theory
  • 2 Theory of computation → Oracles and decision trees
  • Show More...

  • Refine by Keyword
  • 5 Lower Bounds
  • 3 Algebraic Complexity
  • 3 Algebraic circuits
  • 3 arithmetic circuits
  • 2 Algebraic Circuits
  • 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