Search Results

Documents authored by Nagargoje, Satyajeet

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.41
Hilbert Functions and Low-Degree Randomness Extractors

Authors: Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan

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

Abstract
For S ⊆ 𝔽ⁿ, consider the linear space of restrictions of degree-d polynomials to S. The Hilbert function of S, denoted h_S(d,𝔽), is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets S of arbitrary finite grids in 𝔽ⁿ with a fixed size |S|. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size |S|. Understanding the smallest values of Hilbert functions is closely related to the study of degree-d closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-d closures of subsets of 𝔽_qⁿ, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-d closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known.
Cite as

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert Functions and Low-Degree Randomness Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 41:1-41:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2024.41,
  author =	{Golovnev, Alexander and Guo, Zeyu and Hatami, Pooya and Nagargoje, Satyajeet and Yan, Chao},
  title =	{{Hilbert Functions and Low-Degree Randomness Extractors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{41:1--41:24},
  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.41},
  URN =		{urn:nbn:de:0030-drops-210345},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.41},
  annote =	{Keywords: Extractors, Dispersers, Circuits, Hilbert Function, Randomness, Low Degree Polynomials}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.65
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms

Authors: Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi

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

Abstract
Range Avoidance (Avoid) is a total search problem where, given a Boolean circuit 𝖢: {0,1}ⁿ → {0,1}^m, m > n, the task is to find a y ∈ {0,1}^m outside the range of 𝖢. For an integer k ≥ 2, NC⁰_k-Avoid is a special case of Avoid where each output bit of 𝖢 depends on at most k input bits. While there is a very natural randomized algorithm for Avoid, a deterministic algorithm for the problem would have many interesting consequences. Ren, Santhanam, and Wang (FOCS 2022) and Guruswami, Lyu, and Wang (RANDOM 2022) proved that explicit constructions of functions of high formula complexity, rigid matrices, and optimal linear codes, reduce to NC⁰₄-Avoid, thus establishing conditional hardness of the NC⁰₄-Avoid problem. On the other hand, NC⁰₂-Avoid admits polynomial-time algorithms, leaving the question about the complexity of NC⁰₃-Avoid open. We give the first reduction of an explicit construction question to NC⁰₃-Avoid. Specifically, we prove that a polynomial-time algorithm (with an NP oracle) for NC⁰₃-Avoid for the case of m = n+n^{2/3} would imply an explicit construction of a rigid matrix, and, thus, a super-linear lower bound on the size of log-depth circuits. We also give deterministic polynomial-time algorithms for all NC⁰_k-Avoid problems for m ≥ n^{k-1}/log(n). Prior work required an NP oracle, and required larger stretch, m ≥ n^{k-1}.
Cite as

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.APPROX/RANDOM.2023.65,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and Nagargoje, Satyajeet and Saraogi, Sidhant},
  title =	{{Range Avoidance for Constant Depth Circuits: Hardness and Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{65:1--65:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  URN =		{urn:nbn:de:0030-drops-188901},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  annote =	{Keywords: Boolean function analysis, Explicit Constructions, Low-depth Circuits, Range Avoidance, Matrix Rigidity, Circuit Lower Bounds}
}
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 About DROPS Imprint Privacy Contact