On the public citation graph
Polylogarithmic independence fools AC 0 circuits
0 signed · 84 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
inferredcites →https://doi.org/10.1007/bf01940873openalex-snapshot
On deterministic approximation of DNF
inferredcites →https://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/s0020-0190(03)00359-4openalex-snapshot
Almost k-wise independence versus k-wise independence
inferredcites →https://doi.org/10.1109/focs.2007.55openalex-snapshot
Smooth Histograms for Sliding Windows
inferredcites →https://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
inferredcites →https://doi.org/10.1137/070691954openalex-snapshot
Polylogarithmic Independence Can Fool DNF Formulas
inferredcites →https://doi.org/10.1145/1490270.1490273openalex-snapshot
A Simple Proof of Bazzi’s Theorem
inferredcites →https://doi.org/10.1145/174130.174138openalex-snapshot
Constant depth circuits, Fourier transform, and learnability
inferredcites →https://doi.org/10.1145/22145.22196openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/rsa.20991openalex-snapshot
On the probabilistic degree of OR over the reals
inferred← citeshttps://doi.org/10.1007/978-3-030-56877-1_20openalex-snapshot
Interactive Proofs for Social Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-84259-8_17openalex-snapshot
Low-Complexity Weak Pseudorandom Functions in $$\mathtt {AC}0[\mathtt {MOD}2]$$
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_38openalex-snapshot
Pseudorandomness for Linear Length Branching Programs and Stack Machines
inferred← citeshttps://doi.org/10.1007/978-3-662-53015-3_19openalex-snapshot
Fine-Grained Cryptography
inferred← citeshttps://doi.org/10.1007/978-3-662-53015-3_21openalex-snapshot
Bounded Indistinguishability and the Complexity of Recovering Secrets
inferred← citeshttps://doi.org/10.1007/s00037-012-0036-6openalex-snapshot
Pseudorandom Generators for Combinatorial Checkerboards
inferred← citeshttps://doi.org/10.1007/s00037-012-0039-3openalex-snapshot
Bounded-Depth Circuits Cannot Sample Good Codes
inferred← citeshttps://doi.org/10.1007/s00037-012-0051-7openalex-snapshot
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
inferred← citeshttps://doi.org/10.1007/s00037-013-0068-6openalex-snapshot
DNF sparsification and a faster deterministic counting algorithm
inferred← citeshttps://doi.org/10.1007/s00037-015-0100-0openalex-snapshot
Mining Circuit Lower Bound Proofs for Meta-Algorithms
inferred← citeshttps://doi.org/10.1007/s00037-015-0121-8openalex-snapshot
Cryptographic Hardness of Random Local Functions
inferred← citeshttps://doi.org/10.1007/s00037-016-0134-yopenalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1007/s00037-020-00203-wopenalex-snapshot
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels
inferred← citeshttps://doi.org/10.1007/s00037-026-00296-9openalex-snapshot
A Technique for Hardness Amplification Against $$\textsf{AC}^0$$
inferred← citeshttps://doi.org/10.1007/s00224-016-9680-6openalex-snapshot
Small-Bias is Not Enough to Hit Read-Once CNF
inferred← citeshttps://doi.org/10.1016/j.inpa.2021.09.003openalex-snapshot
Texture-based latent space disentanglement for enhancement of a training dataset for ANN-based classification of fruit and vegetables
inferred← citeshttps://doi.org/10.1016/j.tcs.2024.114730openalex-snapshot
Fine-grained polynomial functional encryption
inferred← citeshttps://doi.org/10.1109/ccc.2011.26openalex-snapshot
Improved Constructions of Three Source Extractors
inferred← citeshttps://doi.org/10.1109/ccc.2012.20openalex-snapshot
Hitting Set Generators for Sparse Polynomials over Any Finite Fields
inferred← citeshttps://doi.org/10.1109/ccc.2012.38openalex-snapshot
DNF Sparsification and a Faster Deterministic Counting Algorithm
inferred← citeshttps://doi.org/10.1109/ccc.2014.34openalex-snapshot
Mining Circuit Lower Bound Proofs for Meta-algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2014.39openalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1109/focs.2010.72openalex-snapshot
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields
inferred← citeshttps://doi.org/10.1109/focs.2011.57openalex-snapshot
Pseudorandomness for Read-Once Formulas
inferred← citeshttps://doi.org/10.1109/focs.2014.29openalex-snapshot
Generating k-Independent Variables in Constant Time
inferred← citeshttps://doi.org/10.1109/focs.2015.67openalex-snapshot
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
inferred← citeshttps://doi.org/10.1109/focs.2016.26openalex-snapshot
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy
inferred← citeshttps://doi.org/10.1109/focs.2016.27openalex-snapshot
Extractors for Near Logarithmic Min-Entropy
inferred← citeshttps://doi.org/10.1109/focs.2017.80openalex-snapshot
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time
inferred← citeshttps://doi.org/10.1137/1.9781611974782.73openalex-snapshot
Explicit Resilient Functions Matching Ajtai-Linial
inferred← citeshttps://doi.org/10.1137/120880343openalex-snapshot
Protecting Circuits from Computationally Bounded and Noisy Leakage
inferred← citeshttps://doi.org/10.1137/17m1129088openalex-snapshot
Bounded Independence Plus Noise Fools Products
inferred← citeshttps://doi.org/10.1137/19m1294162openalex-snapshot
On the Probabilistic Degrees of Symmetric Boolean Functions
inferred← citeshttps://doi.org/10.1145/1924421.1924446openalex-snapshot
Poly-logarithmic independence fools bounded-depth boolean circuits
inferred← citeshttps://doi.org/10.1145/2897518.2897528openalex-snapshot
Explicit two-source extractors and resilient functions
inferred← citeshttps://doi.org/10.1145/3095799openalex-snapshot
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
inferred← citeshttps://doi.org/10.1145/3188745.3188822openalex-snapshot
Quantified derandomization of linear threshold circuits
inferred← citeshttps://doi.org/10.1145/3337783openalex-snapshot
Bounded Independence versus Symmetric Tests
inferred← citeshttps://doi.org/10.1145/3357713.3384328openalex-snapshot
A robust version of Hegedus’s lemma, with applications
inferred← citeshttps://doi.org/10.1145/3406325.3451049openalex-snapshot
Expander random walks: a Fourier-analytic approach
inferred← citeshttps://doi.org/10.1145/3564246.3585206openalex-snapshot
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
inferred← citeshttps://doi.org/10.1145/3717823.3718306openalex-snapshot
Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders
inferred← citeshttps://doi.org/10.1145/3798129.3800791openalex-snapshot
High-Accuracy List-Decodable Mean Estimation
inferred← citeshttps://doi.org/10.1145/3798129.3800883openalex-snapshot
Rigorous Implications of the Low-Degree Heuristic
inferred← citeshttps://doi.org/10.1561/0400000109openalex-snapshot
Paradigms for Unconditional Pseudorandom Generators
inferred← citeshttps://doi.org/10.3390/e24070880openalex-snapshot
Recent Advances in Randomness Extraction
inferred← citeshttps://doi.org/10.4230/lipics-approx/random.2021.42openalex-snapshot
On the probabilistic degree of an n-variate boolean function
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2016.24openalex-snapshot
Bounded Independence vs. Moduli
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2016.32openalex-snapshot
On Polynomial Approximations to AC^0
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.54openalex-snapshot
On Closeness to k-Wise Uniformity
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.56openalex-snapshot
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.10openalex-snapshot
Learning Algorithms from Natural Proofs
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2013.201openalex-snapshot
On Improved Degree Lower Bounds for Polynomial Approximation
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.43openalex-snapshot
Expander Random Walks: The General Case and Limitations
inferred← citeshttps://doi.org/10.46298/theoretics.23.5openalex-snapshot
A Robust Version of Heged\H{u}s's Lemma, with Applications
inferred← citeshttps://doi.org/10.48550/arxiv.1205.3534openalex-snapshot
DNF Sparsification and a Faster Deterministic Counting Algorithm
inferred← citeshttps://doi.org/10.48550/arxiv.1408.2157openalex-snapshot
Generating k-independent variables in constant time
inferred← citeshttps://doi.org/10.48550/arxiv.1508.01115openalex-snapshot
Improved Constructions of Two-Source Extractors
inferred← citeshttps://doi.org/10.48550/arxiv.1906.09430openalex-snapshot
Algorithms for Similarity Search and Pseudorandomness
inferred← citeshttps://doi.org/10.7907/3q00-dd64openalex-snapshot
On Quantum Computing and Pseudorandomness
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.