60 Search Results for "Shpilka, Amir"

Volume

LIPIcs, Volume 137

34th Computational Complexity Conference (CCC 2019)

CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA

Editors: Amir Shpilka

Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2024.20
Discreteness of Asymptotic Tensor Ranks (Extended Abstract)

Authors: Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam

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

Abstract
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication algorithms), quantum information (entanglement cost and distillable entanglement), and additive combinatorics (bounds on cap sets, sunflower-free sets, etc.). Examples are the asymptotic tensor rank, asymptotic slice rank and asymptotic subrank. Recent works (Costa-Dalai, Blatter-Draisma-Rupniewski, Christandl-Gesmundo-Zuiddam) have investigated notions of discreteness (no accumulation points) or "gaps" in the values of such tensor parameters. We prove a general discreteness theorem for asymptotic tensor parameters of order-three tensors and use this to prove that (1) over any finite field (and in fact any finite set of coefficients in any field), the asymptotic subrank and the asymptotic slice rank have no accumulation points, and (2) over the complex numbers, the asymptotic slice rank has no accumulation points. Central to our approach are two new general lower bounds on the asymptotic subrank of tensors, which measures how much a tensor can be diagonalized. The first lower bound says that the asymptotic subrank of any concise three-tensor is at least the cube-root of the smallest dimension. The second lower bound says that any concise three-tensor that is "narrow enough" (has one dimension much smaller than the other two) has maximal asymptotic subrank. Our proofs rely on new lower bounds on the maximum rank in matrix subspaces that are obtained by slicing a three-tensor in the three different directions. We prove that for any concise tensor, the product of any two such maximum ranks must be large, and as a consequence there are always two distinct directions with large max-rank.
Cite as

Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam. Discreteness of Asymptotic Tensor Ranks (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.ITCS.2024.20,
  author =	{Bri\"{e}t, Jop and Christandl, Matthias and Leigh, Itai and Shpilka, Amir and Zuiddam, Jeroen},
  title =	{{Discreteness of Asymptotic Tensor Ranks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{20:1--20:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.20},
  URN =		{urn:nbn:de:0030-drops-195483},
  doi =		{10.4230/LIPIcs.ITCS.2024.20},
  annote =	{Keywords: Tensors, Asymptotic rank, Subrank, Slice rank, Restriction, Degeneration, Diagonalization, SLOCC}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.48
Proving Unsatisfiability with Hitting Formulas

Authors: Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals

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

Abstract
A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. Hitting formulas have been studied in many different contexts at least since [Iwama, 1989] and, based on experimental evidence, Peitl and Szeider [Tomás Peitl and Stefan Szeider, 2022] conjectured that unsatisfiable hitting formulas are among the hardest for resolution. Using the fact that hitting formulas are easy to check for satisfiability we make them the foundation of a new static proof system {{rmHitting}}: a refutation of a CNF in {{rmHitting}} is an unsatisfiable hitting formula such that each of its clauses is a weakening of a clause of the refuted CNF. Comparing this system to resolution and other proof systems is equivalent to studying the hardness of hitting formulas. Our first result is that {{rmHitting}} is quasi-polynomially simulated by tree-like resolution, which means that hitting formulas cannot be exponentially hard for resolution and partially refutes the conjecture of Peitl and Szeider. We show that tree-like resolution and {{rmHitting}} are quasi-polynomially separated, while for resolution, this question remains open. For a system that is only quasi-polynomially stronger than tree-like resolution, {{rmHitting}} is surprisingly difficult to polynomially simulate in another proof system. Using the ideas of Raz-Shpilka’s polynomial identity testing for noncommutative circuits [Raz and Shpilka, 2005] we show that {{rmHitting}} is p-simulated by {{rmExtended {{rmFrege}}}}, but we conjecture that much more efficient simulations exist. As a byproduct, we show that a number of static (semi)algebraic systems are verifiable in deterministic polynomial time. We consider multiple extensions of {{rmHitting}}, and in particular a proof system {{{rmHitting}}(⊕)} related to the {{{rmRes}}(⊕)} proof system for which no superpolynomial-size lower bounds are known. {{{rmHitting}}(⊕)} p-simulates the tree-like version of {{{rmRes}}(⊕)} and is at least quasi-polynomially stronger. We show that formulas expressing the non-existence of perfect matchings in the graphs K_{n,n+2} are exponentially hard for {{{rmHitting}}(⊕)} via a reduction to the partition bound for communication complexity. See the full version of the paper for the proofs. They are omitted in this Extended Abstract.
Cite as

Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.ITCS.2024.48,
  author =	{Filmus, Yuval and Hirsch, Edward A. and Riazanov, Artur and Smal, Alexander and Vinyals, Marc},
  title =	{{Proving Unsatisfiability with Hitting Formulas}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-195762},
  doi =		{10.4230/LIPIcs.ITCS.2024.48},
  annote =	{Keywords: hitting formulas, polynomial identity testing, query complexity}
}
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-dev.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.CCC.2023.20
Radical Sylvester-Gallai Theorem for Tuples of Quadratics

Authors: Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Hansen, 1965; Shpilka, 2020]. Hansen’s theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen’s theorem to the setting of quadratic forms in a polynomial ring, where the incidence condition is given by radical membership in a high-codimensional ideal. Our main theorem is also a generalization of the quadratic Sylvester-Gallai Theorem of [Shpilka, 2020]. Our work is the first to prove a radical Sylvester-Gallai type theorem for arbitrary codimension k ≥ 2, whereas previous works [Shpilka, 2020; Shir Peleg and Amir Shpilka, 2020; Shir Peleg and Amir Shpilka, 2021; Garg et al., 2022] considered the case of codimension 2 ideals. Our techniques combine algebraic geometric and combinatorial arguments. A key ingredient is a structural result for ideals generated by a constant number of quadratics, showing that such ideals must be radical whenever the quadratic forms are far apart. Using the wide algebras defined in [Garg et al., 2022], combined with results about integral ring extensions and dimension theory, we develop new techniques for studying such ideals generated by quadratic forms. One advantage of our approach is that it does not need the finer classification theorems for codimension 2 complete intersection of quadratics proved in [Shpilka, 2020; Garg et al., 2022].
Cite as

Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 20:1-20:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2023.20,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Peleg, Shir and Sengupta, Akash Kumar},
  title =	{{Radical Sylvester-Gallai Theorem for Tuples of Quadratics}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{20:1--20:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.20},
  URN =		{urn:nbn:de:0030-drops-182903},
  doi =		{10.4230/LIPIcs.CCC.2023.20},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.22
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

Authors: Suryajith Chillara, Coral Grichener, and Amir Shpilka

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.
Cite as

Suryajith Chillara, Coral Grichener, and Amir Shpilka. On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chillara_et_al:LIPIcs.STACS.2023.22,
  author =	{Chillara, Suryajith and Grichener, Coral and Shpilka, Amir},
  title =	{{On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.22},
  URN =		{urn:nbn:de:0030-drops-176744},
  doi =		{10.4230/LIPIcs.STACS.2023.22},
  annote =	{Keywords: algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.23
Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time

Authors: V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay

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

Abstract
Hrubeš and Wigderson [Hrubeš and Wigderson, 2015] initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, there are deterministic polynomial-time algorithms due to Garg, Gurvits, Oliveira, and Wigderson [Ankit Garg et al., 2016] and Ivanyos, Qiao, and Subrahmanyam [Ivanyos et al., 2018]. A central open problem in this area is to design an efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including concepts from matrix coefficient realization theory [Volčič, 2018] and properties of cyclic division algebras [T.Y. Lam, 2001]. En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas [Michael A. Forbes and Amir Shpilka, 2013] inside a cyclic division algebra of small index.
Cite as

V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay. Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.APPROX/RANDOM.2022.23,
  author =	{Arvind, V. and Chatterjee, Abhranil and Mukhopadhyay, Partha},
  title =	{{Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.23},
  URN =		{urn:nbn:de:0030-drops-171451},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.23},
  annote =	{Keywords: Rational Identity Testing, Black-box Derandomization, Cyclic Division Algebra, Matrix coefficient realization theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.7
𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices

Authors: Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices. Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes. On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.
Cite as

Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7,
  author =	{Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan},
  title =	{{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7},
  URN =		{urn:nbn:de:0030-drops-165695},
  doi =		{10.4230/LIPIcs.CCC.2022.7},
  annote =	{Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.43
Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials

Authors: Shir Peleg and Amir Shpilka

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In this work we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if {𝒬} ⊂ ℂ[x₁.…,x_n] is a finite set, |{𝒬}| = m, of irreducible quadratic polynomials that satisfy the following condition There is δ > 0 such that for every Q ∈ {𝒬} there are at least δ m polynomials P ∈ {𝒬} such that whenever Q and P vanish then so does a third polynomial in {𝒬}⧵{Q,P}. then dim(span) = Poly(1/δ). The work of Barak et al. and Dvir et al. studied the case of linear polynomials and proved an upper bound of O(1/δ) on the dimension (in the first work an upper bound of O(1/δ²) was given, which was improved to O(1/δ) in the second work).
Cite as

Shir Peleg and Amir Shpilka. Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{peleg_et_al:LIPIcs.SoCG.2022.43,
  author =	{Peleg, Shir and Shpilka, Amir},
  title =	{{Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.43},
  URN =		{urn:nbn:de:0030-drops-160515},
  doi =		{10.4230/LIPIcs.SoCG.2022.43},
  annote =	{Keywords: Sylvester-Gallai theorem, quadratic polynomials, Algebraic computation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.26
Bounded Indistinguishability for Simple Sources

Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.
Cite as

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26,
  author =	{Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram},
  title =	{{Bounded Indistinguishability for Simple Sources}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-156223},
  doi =		{10.4230/LIPIcs.ITCS.2022.26},
  annote =	{Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.110
Lower Bounds on Stabilizer Rank

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

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩ = ∑_{j = 1}^r c_j |φ_j⟩ for c_j ∈ ℂ and stabilizer states φ_j. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. We prove a lower bound of Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(√n) of Bravyi, Smith and Smolin [Bravyi et al., 2016]. Further, we prove that for a sufficiently small constant δ, the stabilizer rank of any state which is δ-close to those states is Ω(√n/log n). This is the first non-trivial lower bound for approximate stabilizer rank. Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of 𝔽₂ⁿ, and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.
Cite as

Shir Peleg, Ben Lee Volk, and Amir Shpilka. Lower Bounds on Stabilizer Rank. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 110:1-110:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{peleg_et_al:LIPIcs.ITCS.2022.110,
  author =	{Peleg, Shir and Volk, Ben Lee and Shpilka, Amir},
  title =	{{Lower Bounds on Stabilizer Rank}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{110:1--110:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.110},
  URN =		{urn:nbn:de:0030-drops-157063},
  doi =		{10.4230/LIPIcs.ITCS.2022.110},
  annote =	{Keywords: Quantum Computation, Lower Bounds, Stabilizer rank, Simulation of Quantum computers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.118
Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two

Authors: Gaurav Sinha

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials over finite fields, computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that output gate is an addition gate with in-degree two. Such circuits naturally compute polynomials of the form G×(T₁ + T₂), where G,T₁,T₂ are product of affine forms computed at the first layer in the circuit, and polynomials T₁,T₂ have no common factors. Rank of such a circuit is defined to be the dimension of vector space spanned by all affine factors of T₁ and T₂. For any polynomial f computable by such a circuit, rank(f) is defined to be the minimum rank of any such circuit computing it. Our work develops randomized reconstruction algorithms which take as input black-box access to a polynomial f (over finite field 𝔽), computable by such a circuit. Here are the results. - [Low rank]: When 5 ≤ rank(f) = O(log³ d), it runs in time (nd^{log³d}log |𝔽|)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree ≤ d^{rank(f)}. - [High rank]: When rank(f) = Ω(log³ d), it runs in time (ndlog |𝔽|)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree two. Prior to our work, black-box reconstruction for this circuit class was addressed in [Amir Shpilka, 2007; Karnin and Shpilka, 2009; Sinha, 2016]. Reconstruction algorithm in [Amir Shpilka, 2007] runs in time quasi-polynomial in n,d,|𝔽| and that in [Karnin and Shpilka, 2009] is quasi-polynomial in d,|𝔽|. Algorithm in [Sinha, 2016] works only for polynomials over characteristic zero fields. Thus, ours is the first blackbox reconstruction algorithm for this class of circuits that runs in time polynomial in log |𝔽|. This problem has been mentioned as an open problem in [Ankit Gupta et al., 2012] (STOC 2012). In the high rank case, our algorithm runs in (ndlog|𝔽|)^{O(1)} time, thereby significantly improving the existing algorithms in [Amir Shpilka, 2007; Karnin and Shpilka, 2009].
Cite as

Gaurav Sinha. Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 118:1-118:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sinha:LIPIcs.ITCS.2022.118,
  author =	{Sinha, Gaurav},
  title =	{{Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{118:1--118:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.118},
  URN =		{urn:nbn:de:0030-drops-157143},
  doi =		{10.4230/LIPIcs.ITCS.2022.118},
  annote =	{Keywords: Arithmetic Circuits, Circuit Reconstruction}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.119
Polynomial Identity Testing via Evaluation of Rational Functions

Authors: Dieter van Melkebeek and Andrew Morgan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. In spite of the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas. We study the power of the generator by characterizing its vanishing ideal, i.e., the set of polynomials that it fails to hit. Capitalizing on the univariate nature, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition size of set-multi-linearity in the vanishing ideal. Inspired by an alternating algebra representation, we develop a structured deterministic membership test for the vanishing ideal. As a proof of concept we rederive known derandomization results based on the generator by Shpilka and Volkovich, and present a new application for read-once oblivious arithmetic branching programs that provably transcends the usual combinatorial techniques.
Cite as

Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119,
  author =	{van Melkebeek, Dieter and Morgan, Andrew},
  title =	{{Polynomial Identity Testing via Evaluation of Rational Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{119:1--119:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119},
  URN =		{urn:nbn:de:0030-drops-157158},
  doi =		{10.4230/LIPIcs.ITCS.2022.119},
  annote =	{Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.14
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four

Authors: Suryajith Chillara

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to P_d, then C must have size 2^Ω(√dlog{d}). The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC⁰ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC⁰ can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form - sums of powers of polynomials) of 2^(log^O(1) n) size. Thus they argued that a 2^{ω(polylog n)} "functional" lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the "corresponding Boolean function" of Q against non-uniform ACC⁰. In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log²n) ≤ d ≤ n^{0.01}, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O(d/k²) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (∈ VP) over {0,1}^{n²d} must have size n^Ω(k). Since Iterated Matrix Multiplication IMM_{n,d} over {0,1}^{n²d} is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC⁰ from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMM_{n,d} (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMM_{n,d}, for a slightly larger range of individual degree.
Cite as

Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chillara:LIPIcs.FSTTCS.2021.14,
  author =	{Chillara, Suryajith},
  title =	{{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14},
  URN =		{urn:nbn:de:0030-drops-155251},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.14},
  annote =	{Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.19
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits

Authors: Dori Medini and Amir Shpilka

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
In this paper we study polynomials in VP_{e} (polynomial-sized formulas) and in ΣΠΣ (polynomial-size depth-3 circuits) whose orbits, under the action of the affine group GL^{aff}_n(𝔽) (the action of (A,b) ∈ GL^{aff}_n(𝔽) on a polynomial f ∈ 𝔽[x] is defined as (A,b)∘f = f(A^Tx+b)), are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. Specifically, we obtain the following results: 1) For C_n(ℓ_1(x),…,ℓ_n(x)) ≜ Trace(\begin{pmatrix} 𝓁₁(x) & 1 \\ 1 & 0 \end{pmatrix} ⋅ … ⋅ \begin{pmatrix} 𝓁_n(x) & 1 \\ 1 & 0 \end{pmatrix}), where the 𝓁_is are linearly independent linear functions, we construct a polynomial-sized interpolating set, and give a polynomial-time reconstruction algorithm. By a result of Bringmann, Ikenmeyer and Zuiddam, the set of all such polynomials is dense in VP_e [Karl Bringmann et al., 2018], thus our construction gives the first polynomial-size interpolating set for a dense subclass of VP_e. 2) For polynomials of the form ANF_Δ(𝓁₁(x),…,𝓁_{4^Δ}(x)), where ANF_Δ(x) is the canonical read-once formula in alternating normal form, of depth 2Δ, and the 𝓁_is are linearly independent linear functions, we provide a quasipolynomial-size interpolating set. We also observe that the reconstruction algorithm of [Ankit Gupta et al., 2014] works for all polynomials in this class. This class is also dense in VP_e. 3) Similarly, we give a quasipolynomial-sized hitting set for read-once formulas (not necessarily in alternating normal form) composed with a set of linearly independent linear functions. This gives another dense class in VP_e. 4) We give a quasipolynomial-sized hitting set for polynomials of the form f(𝓁₁(x),…,𝓁_{m}(x)), where f is an m-variate s-sparse polynomial. and the 𝓁_is are linearly independent linear functions in n ≥ m variables. This class is dense in ΣΠΣ. 5) For polynomials of the form ∑_{i=1}^{s}∏_{j=1}^{d}𝓁_{i,j}(x), where the 𝓁_{i,j}s are linearly independent linear functions, we construct a polynomial-sized interpolating set. We also observe that the reconstruction algorithm of [Neeraj Kayal and Chandan Saha, 2019] works for every polynomial in the class. This class is dense in ΣΠΣ. As VP = VNC², our results for VP_{e} translate immediately to VP with a quasipolynomial blow up in parameters. If any of our hitting or interpolating sets could be made robust then this would immediately yield a hitting set for the superclass in which the relevant class is dense, and as a consequence also a lower bound for the superclass. Unfortunately, we also prove that the kind of constructions that we have found (which are defined in terms of k-independent polynomial maps) do not necessarily yield robust hitting sets.
Cite as

Dori Medini and Amir Shpilka. Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 19:1-19:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{medini_et_al:LIPIcs.CCC.2021.19,
  author =	{Medini, Dori and Shpilka, Amir},
  title =	{{Hitting Sets and Reconstruction for Dense Orbits in VP\underline\{e\} and \Sigma\Pi\Sigma Circuits}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{19:1--19:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.19},
  URN =		{urn:nbn:de:0030-drops-142930},
  doi =		{10.4230/LIPIcs.CCC.2021.19},
  annote =	{Keywords: Algebraic complexity, VP, VNP, algebraic circuits, algebraic formula}
}
  • Refine by Author
  • 13 Shpilka, Amir
  • 5 Peleg, Shir
  • 5 Volk, Ben Lee
  • 3 Kumar, Mrinal
  • 3 Lovett, Shachar
  • Show More...

  • Refine by Classification
  • 18 Theory of computation → Algebraic complexity theory
  • 9 Theory of computation → Circuit complexity
  • 7 Theory of computation
  • 6 Theory of computation → Pseudorandomness and derandomization
  • 3 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 6 Derandomization
  • 4 Lower Bounds
  • 4 Polynomial Identity Testing
  • 3 Algebraic Complexity
  • 3 Arithmetic Circuits
  • Show More...

  • Refine by Type
  • 59 document
  • 1 volume

  • Refine by Publication Year
  • 36 2019
  • 7 2022
  • 5 2020
  • 4 2021
  • 3 2024
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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