Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a lowdegree polynomial map 𝑓 to an element sampled uniformly at random from a 𝑘dimensional variety 𝑉. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012). Assuming certain natural nondegeneracy conditions on the map 𝑓 and the variety 𝑉 , which in particular ensure that the source has enough minentropy, we extract almost all the minentropy of the distribution. Unlike the Dvir–Gabizon–Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a byproduct, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras. Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.more » « less

We show that there is an equation of degree at most poly( n ) for the (Zariski closure of the) set of the nonrigid matrices: That is, we show that for every large enough field 𝔽, there is a nonzero n 2 variate polynomial P ε 𝔽[ x 1, 1 , ..., x n, n ] of degree at most poly( n ) such that every matrix M that can be written as a sum of a matrix of rank at most n /100 and a matrix of sparsity at most n 2 /100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [ 9 ] and improves the best upper bound known for this problem down from exp ( n 2 ) [ 9 , 12 ] to poly( n ). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n 2 /200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [ 21 ] to construct lowdegree “universal” maps for nonrigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a lowdegree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [ 11 ].more » « less

The stabilizer rank of a quantum state ψ is the minimal r such that  ψ ⟩ = ∑ j = 1 r c j  φ j ⟩ for c j ∈ C 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 singlequbit 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 \cite{BSS16}. 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 nontrivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F 2 n , 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 RazborovSmolensky low degree polynomial approximations and correlation bounds against the majority function.more » « less