16 Search Results for "Goodman, Jesse"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.73
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We construct a family of distributions {𝒟_n}_n with 𝒟_n over {0, 1}ⁿ and a family of depth-7 quantum circuits {C_n}_n such that 𝒟_n is produced exactly by C_n with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance 1 - e^{-Ω(n)} from 𝒟_n. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems.
Cite as

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.ITCS.2026.73,
  author =	{Grier, Daniel and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony and Wu, Kewen},
  title =	{{Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.73},
  URN =		{urn:nbn:de:0030-drops-253607},
  doi =		{10.4230/LIPIcs.ITCS.2026.73},
  annote =	{Keywords: Shallow circuits, sampling, quantum circuits}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.33
Bit-Fixing Extractors for Almost-Logarithmic Entropy

Authors: Dean Doron and Ori Fridman

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

Abstract
An oblivious bit-fixing source is a distribution over {0,1}ⁿ, where k bits are uniform and independent and the rest n-k are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity theory. We construct explicit extractors for oblivious bit-fixing source that support k = Õ(log n), outputting almost all the entropy with low error. The previous state-of-the-art construction that outputs many bits is due to Rao [Rao, CCC '09], and requires entropy k ≥ log^{c} n for some large constant c. The two key components in our constructions are new low-error affine condensers for poly-logarithmic entropies (that we achieve using techniques from the nonmalleable extractors literature), and a dual use of linear condensers for OBF sources.
Cite as

Dean Doron and Ori Fridman. Bit-Fixing Extractors for Almost-Logarithmic Entropy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.33,
  author =	{Doron, Dean and Fridman, Ori},
  title =	{{Bit-Fixing Extractors for Almost-Logarithmic Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.33},
  URN =		{urn:nbn:de:0030-drops-243994},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.33},
  annote =	{Keywords: Seedless extractors, oblivious bit-fixing sources}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.38
Low-Degree Polynomials Are Good Extractors

Authors: Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro

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

Abstract
We prove that random low-degree polynomials (over 𝔽₂) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following. 1) Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial and variety sources via a single unified approach. 2) Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). Formally, for any even d, we show that a random degree d polynomial is an ε-error extractor for n-bit sumset sources with min-entropy k = O(d(n/ε²)^{2/d}). This is nearly tight in the polynomial error regime. Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof may be of independent interest. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024).
Cite as

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro. Low-Degree Polynomials Are Good Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 38:1-38:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.APPROX/RANDOM.2025.38,
  author =	{Alrabiah, Omar and Goodman, Jesse and Mosheiff, Jonathan and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Are Good Extractors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{38:1--38:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.38},
  URN =		{urn:nbn:de:0030-drops-244048},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.38},
  annote =	{Keywords: randomness extractors, low-degree polynomials, local sources, polynomial sources, variety sources, sumset sources, sumset extractors, Reed-Muller codes, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.3
Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places

Authors: Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
Can Shamir’s secret-sharing protect its secret even when all shares are partially compromised? For instance, repairing Reed-Solomon codewords, when possible, recovers the entire secret in the corresponding Shamir’s secret sharing. Yet, Shamir’s secret sharing mitigates various side-channel threats, depending on where its "secret-sharing polynomial" is evaluated. Although most evaluation places yield secure schemes, none are known explicitly; even techniques to identify them are unknown. Our work initiates research into such classifier constructions and derandomization objectives. In this work, we focus on Shamir’s scheme over prime fields, where every share is required to reconstruct the secret. We investigate the security of these schemes against single-bit probes into shares stored in their native binary representation. Technical analysis is particularly challenging when dealing with Reed-Solomon codewords over prime fields, as observed recently in the code repair literature. Furthermore, ensuring the statistical independence of the leakage from the secret necessitates the elimination of any subtle correlations between them. In this context, we present: 1) An efficient algorithm to classify evaluation places as secure or vulnerable against the least-significant-bit leakage. 2) Modulus choices where the classifier above extends to any single-bit probe per share. 3) Explicit modulus choices and secure evaluation places for them. On the way, we discover new bit-probing attacks on Shamir’s scheme, revealing surprising correlations between the leakage and the secret, leading to vulnerabilities when choosing evaluation places naïvely. Our results rely on new techniques to analyze the security of secret-sharing schemes against side-channel threats. We connect their leakage resilience to the orthogonality of square wave functions, which, in turn, depends on the 2-adic valuation of rational approximations. These techniques, novel to the security analysis of secret sharings, can potentially be of broader interest.
Cite as

Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye. Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.ITC.2025.3,
  author =	{Hwang, Jihun and Maji, Hemanta K. and Nguyen, Hai H. and Ye, Xiuyu},
  title =	{{Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.3},
  URN =		{urn:nbn:de:0030-drops-243531},
  doi =		{10.4230/LIPIcs.ITC.2025.3},
  annote =	{Keywords: Shamir’s secret sharing, leakage resilience, physical bit probing, secure evaluation places, secure modulus choice, square wave families, LLL algorithm, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.30
Online Condensing of Unpredictable Sources via Random Walks

Authors: Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
A natural model of a source of randomness consists of a long stream of symbols X = X_1∘…∘X_t, with some guarantee on the entropy of X_i conditioned on the outcome of the prefix x_1,… ,x_{i-1}. We study unpredictable sources, a generalization of the almost Chor-Goldreich (CG) sources considered in [Doron et al., 2023]. In an unpredictable source X, for a typical draw of x ∼ X, for most i-s, the element x_i has a low probability of occurring given x_1,… ,x_{i-1}. Such a model relaxes the often unrealistic assumption of a CG source that for every i, and every x_1,… ,x_{i-1}, the next symbol X_i has sufficiently large entropy. Unpredictable sources subsume all previously considered notions of almost CG sources, including notions that [Doron et al., 2023] failed to analyze, and including those that are equivalent to general sources with high min entropy. For a lossless expander G = (V,E) with m = log |V|, we consider a random walk V_0,V_1,…,V_t on G using unpredictable instructions that have sufficient entropy with respect to m. Our main theorem is that for almost all the steps t/2 ≤ i ≤ t in the walk, the vertex V_i is close to a distribution with min-entropy at least m-O(1). As a result, we obtain seeded online condensers with constant entropy gap, and seedless (deterministic) condensers outputting a constant fraction of the entropy. In particular, our condensers run in space comparable to the output entropy, as opposed to the size of the stream, and even when the length t of the stream is not known ahead of time. As another corollary, we obtain a new extractor based on expander random walks handling lower entropy than the classic expander based construction relying on spectral techniques [Gillman, 1998]. As our main technical tool, we provide a novel analysis covering a key case of adversarial random walks on lossless expanders that [Doron et al., 2023] fails to address. As part of the analysis, we provide a "chain rule for vertex probabilities". The standard chain rule states that for every x ∼ X and i, Pr(x_1,… ,x_i) = Pr[X_i = x_i|X_[1,i-1] = x_1,… ,x_{i-1}] ⋅ Pr(x_1,… ,x_{i-1}). If W(x₁,… ,x_i) is the vertex reached using x₁,… ,x_i, then the chain rule for vertex probabilities essentially states that the same phenomena occurs for a typical x: Pr [V_i = W(x_1,… ,x_i)] ≲ Pr[X_i = x_i|X_[1,i-1] = x_1,… ,x_{i-1}] ⋅ Pr[V_{i-1} = W(x_1,… ,x_{i-1})], where V_i is the vertex distribution of the random walk at step i using X.
Cite as

Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Online Condensing of Unpredictable Sources via Random Walks. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.CCC.2025.30,
  author =	{Doron, Dean and Moshkovitz, Dana and Oh, Justin and Zuckerman, David},
  title =	{{Online Condensing of Unpredictable Sources via Random Walks}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.30},
  URN =		{urn:nbn:de:0030-drops-237243},
  doi =		{10.4230/LIPIcs.CCC.2025.30},
  annote =	{Keywords: Randomness Extractors, Expander Graphs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.1
List Decoding Quotient Reed-Muller Codes

Authors: Omri Gotlib, Tali Kaufman, and Shachar Lovett

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Reed-Muller codes consist of evaluations of n-variate polynomials over a finite field 𝔽 with degree at most d. Much like every linear code, Reed-Muller codes can be characterized by constraints, where a codeword is valid if and only if it satisfies all degree-d constraints. For a subset X̃ ⊆ 𝔽ⁿ, we introduce the notion of X̃-quotient Reed-Muller code. A function F:X̃ → 𝔽 is a valid codeword in the quotient code if it satisfies all the constraints of degree-d polynomials lying in X̃. This gives rise to a novel phenomenon: a quotient codeword may have many extensions to original codewords. This weakens the connection between original codewords and quotient codewords which introduces a richer range of behaviors along with substantial new challenges. Our goal is to answer the following question: what properties of X̃ will imply that the quotient code inherits its distance and list-decoding radius from the original code? We address this question using techniques developed by Bhowmick and Lovett [Abhishek Bhowmick and Shachar Lovett, 2014], identifying key properties of 𝔽ⁿ used in their proof and extending them to general subsets X̃ ⊆ 𝔽ⁿ. By introducing a new tool, we overcome the novel challenge in analyzing the quotient code that arises from the weak connection between original and quotient codewords. This enables us to apply known results from additive combinatorics and algebraic geometry [David Kazhdan and Tamar Ziegler, 2018; David Kazhdan and Tamar Ziegler, 2019; Amichai Lampert and Tamar Ziegler, 2021] to show that when X̃ is a high rank variety, X̃-quotient Reed-Muller codes inherit the distance and list-decoding parameters from the original Reed-Muller codes.
Cite as

Omri Gotlib, Tali Kaufman, and Shachar Lovett. List Decoding Quotient Reed-Muller Codes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 1:1-1:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.CCC.2025.1,
  author =	{Gotlib, Omri and Kaufman, Tali and Lovett, Shachar},
  title =	{{List Decoding Quotient Reed-Muller Codes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{1:1--1:44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.1},
  URN =		{urn:nbn:de:0030-drops-236957},
  doi =		{10.4230/LIPIcs.CCC.2025.1},
  annote =	{Keywords: Reed-Muller Codes, Quotient Code, Quotient Reed-Muller Code, List Decoding, High Rank Variety, High-Order Fourier Analysis, Error-Correcting Codes}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.7
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

Authors: Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study a novel question about nonlocal quantum state discrimination: how well can non-communicating - but entangled - players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is to show that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We show that this question has implications to unclonable cryptography, which leverages the no-cloning principle to build cryptographic primitives that are classically impossible to achieve. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We leverage our main result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing. These applications present evidence that simultaneous Haar indistinguishability could be useful in quantum cryptography.
Cite as

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITCS.2025.7,
  author =	{Ananth, Prabhanjan and Kaleoglu, Fatih and Yuen, Henry},
  title =	{{Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.7},
  URN =		{urn:nbn:de:0030-drops-226352},
  doi =		{10.4230/LIPIcs.ITCS.2025.7},
  annote =	{Keywords: Quantum, Haar, unclonable encryption}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.68
New Pseudorandom Generators and Correlation Bounds Using Extractors

Authors: Vinayak M. Kumar

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalization of structured low-degree 𝔽₂-polynomials that we did not have correlation bounds for before. In particular: - We construct a PRG for width-2 poly(n)-length branching programs which read d bits at a time with seed length 2^O(√{log n}) ⋅ d²log²(1/ε). This comes quadratically close to optimal dependence in d and log(1/ε). Improving the dependence on n would imply nontrivial PRGs for log n-degree 𝔽₂-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on d with seed length of O(dlog n + d2^dlog(1/ε)). - We provide the first nontrivial (and nearly optimal) correlation bounds and PRGs against size-n^Ω(log n) AC⁰ circuits with either n^{.99} SYM gates (computing an arbitrary symmetric function) or n^{.49} THR gates (computing an arbitrary linear threshold function). This is a generalization of sparse 𝔽₂-polynomials, which can be simulated by an AC⁰ circuit with one parity gate at the top. Previous work of Servedio and Tan only handled n^{.49} SYM gates or n^{.24} THR gates, and previous work of Lovett and Srinivasan only handled polynomial-size circuits. - We give exponentially small correlation bounds against degree-n^O(1) 𝔽₂-polynomials which are set-multilinear over some arbitrary partition of the input into n^{1-O(1)} parts (noting that at n parts, we recover all low degree polynomials). This vastly generalizes correlation bounds against degree-d polynomials which are set-multilinear over a fixed partition into d blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty, and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds for more general models of computation. Although this technique has been used in previous work, they rely on the model simplifying drastically under random restrictions. We view our results as a proof of concept that such fortification can be done even for classes that do not enjoy such behavior.
Cite as

Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.ITCS.2025.68,
  author =	{Kumar, Vinayak M.},
  title =	{{New Pseudorandom Generators and Correlation Bounds Using Extractors}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{68:1--68:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.68},
  URN =		{urn:nbn:de:0030-drops-226961},
  doi =		{10.4230/LIPIcs.ITCS.2025.68},
  annote =	{Keywords: Pseudorandom Generators, Correlation Bounds, Constant-Depth Circuits}
}
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.2024.44
Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields

Authors: Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk

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

Abstract
We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field 𝔽_q. The seed length of our generators is O(d log n + log q), over fields of size exponential in d and characteristic at least d(d-1)+1. Previous constructions such as Bogdanov’s (STOC 2005) and Derksen and Viola’s (FOCS 2022) had either suboptimal seed length or required the field size to depend on n. Our approach follows Bogdanov’s paradigm while incorporating techniques from Lecerf’s factorization algorithm (J. Symb. Comput. 2007) and insights from the construction of Derksen and Viola regarding the role of indecomposability of polynomials.
Cite as

Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dwivedi_et_al:LIPIcs.APPROX/RANDOM.2024.44,
  author =	{Dwivedi, Ashish and Guo, Zeyu and Volk, Ben Lee},
  title =	{{Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{44:1--44:19},
  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.44},
  URN =		{urn:nbn:de:0030-drops-210370},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.44},
  annote =	{Keywords: Pseudorandom Generators, Low Degree Polynomials}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.5
Explicit Time and Space Efficient Encoders Exist Only with Random Access

Authors: Joshua Cook and Dana Moshkovitz

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time n^{1 + o(1)} and space polylog(n) provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [Divsalar et al., 1998] and the codes described in [Gál et al., 2013]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length. In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access.
Cite as

Joshua Cook and Dana Moshkovitz. Explicit Time and Space Efficient Encoders Exist Only with Random Access. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.CCC.2024.5,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Explicit Time and Space Efficient Encoders Exist Only with Random Access}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{5:1--5:54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.5},
  URN =		{urn:nbn:de:0030-drops-204015},
  doi =		{10.4230/LIPIcs.CCC.2024.5},
  annote =	{Keywords: Time-Space Trade Offs, Error Correcting Codes, Encoders, Explicit Constructions, Streaming Lower Bounds, Sequential Access, Time-Space Lower Bounds, Lossless Condensers, Invertible Condensers, Condensers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.28
Extractors for Polynomial Sources over 𝔽₂

Authors: Eshan Chattopadhyay, Jesse Goodman, and Mohit Gurumukhani

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

Abstract
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.
Cite as

Eshan Chattopadhyay, Jesse Goodman, and Mohit Gurumukhani. Extractors for Polynomial Sources over 𝔽₂. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2024.28,
  author =	{Chattopadhyay, Eshan and Goodman, Jesse and Gurumukhani, Mohit},
  title =	{{Extractors for Polynomial Sources over \mathbb{F}₂}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{28:1--28:24},
  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.28},
  URN =		{urn:nbn:de:0030-drops-195569},
  doi =		{10.4230/LIPIcs.ITCS.2024.28},
  annote =	{Keywords: Extractors, low-degree polynomials, varieties, sumset extractors}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.3
Knowledge Engineering Using Large Language Models

Authors: Bradley P. Allen, Lise Stork, and Paul Groth

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Knowledge engineering is a discipline that focuses on the creation and maintenance of processes that generate and apply knowledge. Traditionally, knowledge engineering approaches have focused on knowledge expressed in formal languages. The emergence of large language models and their capabilities to effectively work with natural language, in its broadest sense, raises questions about the foundations and practice of knowledge engineering. Here, we outline the potential role of LLMs in knowledge engineering, identifying two central directions: 1) creating hybrid neuro-symbolic knowledge systems; and 2) enabling knowledge engineering in natural language. Additionally, we formulate key open research questions to tackle these directions.
Cite as

Bradley P. Allen, Lise Stork, and Paul Groth. Knowledge Engineering Using Large Language Models. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.1.1.3,
  author =	{Allen, Bradley P. and Stork, Lise and Groth, Paul},
  title =	{{Knowledge Engineering Using Large Language Models}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.3},
  URN =		{urn:nbn:de:0030-drops-194777},
  doi =		{10.4230/TGDK.1.1.3},
  annote =	{Keywords: knowledge engineering, large language models}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.36
Sampling and Certifying Symmetric Functions

Authors: Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov

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

Abstract
A circuit 𝒞 samples a distribution X with an error ε if the statistical distance between the output of 𝒞 on the uniform input and X is ε. We study the hardness of sampling a uniform distribution over the set of n-bit strings of Hamming weight k denoted by Uⁿ_k for decision forests, i.e. every output bit is computed as a decision tree of the inputs. For every k there is an O(log n)-depth decision forest sampling Uⁿ_k with an inverse-polynomial error [Emanuele Viola, 2012; Czumaj, 2015]. We show that for every ε > 0 there exists τ such that for decision depth τ log (n/k) / log log (n/k), the error for sampling U_kⁿ is at least 1-ε. Our result is based on the recent robust sunflower lemma [Ryan Alweiss et al., 2021; Rao, 2019]. Our second result is about matching a set of n-bit strings with the image of a d-local circuit, i.e. such that each output bit depends on at most d input bits. We study the set of all n-bit strings whose Hamming weight is at least n/2. We improve the previously known locality lower bound from Ω(log^* n) [Beyersdorff et al., 2013] to Ω(√log n), leaving only a quartic gap from the best upper bound of O(log² n).
Cite as

Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36,
  author =	{Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry},
  title =	{{Sampling and Certifying Symmetric Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{36:1--36:21},
  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.36},
  URN =		{urn:nbn:de:0030-drops-188611},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.36},
  annote =	{Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.10
Low-Degree Polynomials Extract From Local Sources

Authors: Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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.
Cite as

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10,
  author =	{Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Extract From Local Sources}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10},
  URN =		{urn:nbn:de:0030-drops-163519},
  doi =		{10.4230/LIPIcs.ICALP.2022.10},
  annote =	{Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning}
}
  • Refine by Type
  • 16 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 4 2024
  • 2 2023
  • 2 2022

  • Refine by Author
  • 4 Goodman, Jesse
  • 3 Chattopadhyay, Eshan
  • 2 Alrabiah, Omar
  • 2 Doron, Dean
  • 2 Guo, Zeyu
  • Show More...

  • Refine by Series/Journal
  • 15 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 6 Theory of computation → Pseudorandomness and derandomization
  • 4 Theory of computation → Expander graphs and randomness extractors
  • 3 Theory of computation → Circuit complexity
  • 2 Theory of computation → Error-correcting codes
  • 1 Computing methodologies → Machine learning
  • Show More...

  • Refine by Keyword
  • 3 low-degree polynomials
  • 3 lower bounds
  • 2 Extractors
  • 2 Low Degree Polynomials
  • 2 Pseudorandom Generators
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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