More Like this

1. Polynomial Identity Testing via Evaluation of Rational Functions

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

   van Melkebeek, Dieter; Morgan, Andrew (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   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. 

   more » « less
2. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols

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

   van Melkebeek, Dieter; Mocelin Sdroievski, Nicollas (July 2023, Proceedings of the 38th Computational Complexity Conference (CCC 2023))

   Ta-Shma, Amnon (Ed.)

   A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settings blackbox derandomization, i.e., derandomization through pseudo-random generators, has been shown equivalent to lower bounds for decision problems against circuits. Recently, Chen and Tell (FOCS'21) established near-equivalences in the BPP setting between whitebox derandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function f on the given instance. In this paper we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness to derandomization direction, consider a length-preserving function f computable by a nondeterministic algorithm that runs in time n^a. We show that if every Arthur-Merlin protocol that runs in time n^c for c = O(log² a) can only compute f correctly on finitely many inputs, then AM is in NP. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs for nondeterministic computations. As a byproduct of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). Byproducts in the average-case setting include the first uniform hardness vs. randomness tradeoffs for AM, as well as an unconditional mild derandomization result for AM. 

   more » « less
3. Instance-Wise Hardness and Refutation versus Derandomization for Arthur-Merlin Protocols

   https://doi.org/10.1007/s00037-025-00279-2  

   van_Melkebeek, Dieter; Mocelin_Sdroievski, Nicollas (December 2025, computational complexity)

   Abstract A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settingsblackboxderandomization, i.e., derandomization through pseudorandom generators, has been shown equivalent to lower bounds for decision problems against circuits.Recently, Chen and Tell (FOCS'21) established nearequivalences in the BPP setting betweenwhiteboxderandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function$$f$$ $f$on the given instance. Follow-up works managed to obtain full equivalences in the BPP setting by exploiting acompressionproperty of classical pseudorandom generator constructions. In particular, Chen, Tell, and Williams (FOCS'23) showed that derandomization of BPP is equivalent toconstructivelower bounds against algorithms that go through a compression phase.In this paper, we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness-to-derandomization direction, consider a length-preserving function$$f$$ $f$computable by a nondeterministic algorithm that runs in time$$n^a$$ $n^a$. We show that if every Arthur-Merlin protocol that runs in time$$n^c$$ $n^c$for$$c=O(\log^2 a)$$ $c=O\left({log}^{2}a\right)$can only compute$$f$$ $f$correctly on finitely many inputs, then AM is in NP. We also obtain equivalences between constructive lower bounds against Arthur-Merlin protocols that go through a compression phase and derandomization of AM viatargetedgenerators. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs of proximity for nondeterministic computations. As a by-product of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). By-products in the average-case setting include the first uniform hardness vs. randomness trade-offs for AM, as well as an unconditional mild derandomization result for AM. 

   more » « less
4. Improved Hitting Set for Orbit of ROABPs

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.30  

   Bhargava, Vishwas; Ghosh, Sumanta (September 2021, Leibniz international proceedings in informatics)

   Wootters, Mary; Sanita, Laura (Ed.)

   The orbit of an n-variate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets. 

   more » « less
5. Quantitative Hilbert Irreducibility and Almost Prime Values of Polynomial Discriminants

   https://doi.org/10.1093/imrn/rnab296  

   Anderson, Theresa C; Gafni, Ayla; Lemke Oliver, Robert J; Lowry-Duda, David; Shakan, George; Zhang, Ruixiang (November 2021, International Mathematics Research Notices)

   Abstract We study two polynomial counting questions in arithmetic statistics via a combination of Fourier analytic and arithmetic methods. First, we obtain new quantitative forms of Hilbert’s Irreducibility Theorem for degree $$n$$ polynomials $$f$$ with $$\textrm {Gal}(f) \subseteq A_n$$. We study this both for monic polynomials and non-monic polynomials. Second, we study lower bounds on the number of degree $$n$$ monic polynomials with almost prime discriminants, as well as the closely related problem of lower bounds on the number of degree $$n$$ number fields with almost prime discriminants. 

   more » « less