More Like this

1. Extractors for Polynomial Sources over 𝔽₂

   https://doi.org/10.4230/LIPIcs.ITCS.2024.28  

   Chattopadhyay, Eshan; Goodman, Jesse; Gurumukhani, Mohit (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   We explicitly construct the first nontrivial extractors for degree d ≥ 2 polynomial sources over 𝔽₂. Our extractor requires min-entropy k ≥ n - (√{log n})/((log log n / d)^{d/2}). Previously, no constructions were known, even for min-entropy k ≥ n-1. A key ingredient in our construction is an input reduction lemma, which allows us to assume that any polynomial source with min-entropy k can be generated by O(k) uniformly random bits. We also provide strong formal evidence that polynomial sources are unusually challenging to extract from, by showing that even our most powerful general purpose extractors cannot handle polynomial sources with min-entropy below k ≥ n-o(n). In more detail, we show that sumset extractors cannot even disperse from degree 2 polynomial sources with min-entropy k ≥ n-O(n/log log n). In fact, this impossibility result even holds for a more specialized family of sources that we introduce, called polynomial non-oblivious bit-fixing (NOBF) sources. Polynomial NOBF sources are a natural new family of algebraic sources that lie at the intersection of polynomial and variety sources, and thus our impossibility result applies to both of these classical settings. This is especially surprising, since we do have variety extractors that slightly beat this barrier - implying that sumset extractors are not a panacea in the world of seedless extraction. 

   more » « less
2. Some bounds arising from a polynomial ideal associated to any $$t$$-design

   https://doi.org/10.13069/jacodesmath.729446  

   MARTIN, William J; STINSON, Douglas R (May 2020, Journal of Algebra Combinatorics Discrete Structures and Applications)

   null (Ed.)

   We consider ordered pairs (X,B) where X is a finite set of size v and B is some collection of k-element subsets of X such that every t-element subset of X is contained in exactly λ "blocks'' b ∈B for some fixed λ. We represent each block b by a zero-one vector c_b of length v and explore the ideal I(B) of polynomials in v variables with complex coefficients which vanish on the set { c_b ∣ b ∈ B}. After setting up the basic theory, we investigate two parameters related to this ideal: γ1(B) is the smallest degree of a non-trivial polynomial in the ideal I(B) and γ2(B) is the smallest integer s such that I(B) is generated by a set of polynomials of degree at most s. We first prove the general bounds t/2 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k. 

   more » « less
3. Approximate Degree Lower Bounds for Oracle Identification Problems

   Bun, Mark; Voronova, Nadezhda (July 2023, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023))

   Fawzi, Omar; Walter, Michael (Ed.)

   The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x ∈ {0, 1}ⁿ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of x. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log² n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions. 

   more » « less
4. Low-Degree Polynomials Extract From Local Sources

   Alrabiah, Omar; Chattopadhyay, Eshan; Goodman, Jesse; Li, Xin; Ribeiro, Joao (January 2022, Leibniz international proceedings in informatics)

   Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (Ed.)

   We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem. 

   more » « less
5. On correlation bounds against polynomials Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.3  

   Ivanov, Peter; Pavlovic, Liam; Viola, Emanuele (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric. 

   more » « less