On the public citation graph
Hardness Amplification Proofs Require Majority
0 signed · 131 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.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferredcites →https://doi.org/10.1006/jcss.2001.1780openalex-snapshot
Randomness vs Time: Derandomization under a Uniform Assumption
inferredcites →https://doi.org/10.1007/11682462_52openalex-snapshot
Hardness Amplification Via Space-Efficient Direct Products
inferredcites →https://doi.org/10.1007/978-3-540-28629-5_24openalex-snapshot
Some Meet-in-the-Middle Circuit Lower Bounds
inferredcites →https://doi.org/10.1007/978-3-540-30576-7_3openalex-snapshot
On Hardness Amplification of One-Way Functions
inferredcites →https://doi.org/10.1007/978-3-540-73420-8_18openalex-snapshot
On the Complexity of Hard-Core Set Constructions
inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01215346openalex-snapshot
The expressive power of voting polynomials
inferredcites →https://doi.org/10.1007/bf01262928openalex-snapshot
On the hardness of computing the permanent of random matrices
inferredcites →https://doi.org/10.1007/bf01263420openalex-snapshot
When do extra majority gates help? Polylog (N) majority gates are equivalent to one
inferredcites →https://doi.org/10.1007/bf01272517openalex-snapshot
On the power of small-depth threshold circuits
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bf01375474openalex-snapshot
Pseudorandom bits for constant depth circuits
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/s00037-001-8195-xopenalex-snapshot
Communication complexity towards lower bounds on circuit depth
inferredcites →https://doi.org/10.1007/s00037-004-0187-1openalex-snapshot
The complexity of constructing pseudorandom generators from hard functions
inferredcites →https://doi.org/10.1007/s00037-007-0218-9openalex-snapshot
Pseudorandomness for Approximate Counting and Sampling
inferredcites →https://doi.org/10.1007/s00037-007-0233-xopenalex-snapshot
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
inferredcites →https://doi.org/10.1007/s00037-009-0267-3openalex-snapshot
On Approximate Majority and Probabilistic Time
inferredcites →https://doi.org/10.1016/0020-0190(93)90041-7openalex-snapshot
nω(log n) lower bounds on the size of depth-3 threshold cicuits with AND gates at the bottom
inferredcites →https://doi.org/10.1016/0020-0190(94)00171-topenalex-snapshot
Lower bounds for sampling algorithms for estimating the average
inferredcites →https://doi.org/10.1016/0022-0000(92)90047-mopenalex-snapshot
Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs
inferredcites →https://doi.org/10.1016/0022-0000(93)90001-dopenalex-snapshot
Threshold circuits of bounded depth
inferredcites →https://doi.org/10.1016/0168-0072(83)90038-6openalex-snapshot
∑11-Formulae on finite structures
inferredcites →https://doi.org/10.1016/j.crma.2005.03.008openalex-snapshot
Estimation of certain exponential sums arising in complexity theory
inferredcites →https://doi.org/10.1016/j.crma.2005.07.011openalex-snapshot
Bounds on an exponential sum arising in Boolean circuit complexity
inferredcites →https://doi.org/10.1016/j.jcss.2004.01.001openalex-snapshot
Hardness amplification within NP
inferredcites →https://doi.org/10.1016/j.tcs.2006.10.009openalex-snapshot
Improved hardness amplification in NP
inferredcites →https://doi.org/10.1023/a:1022949332276openalex-snapshot
Boosting and Hard-Core Set Construction
inferredcites →https://doi.org/10.1090/dimacs/013/01openalex-snapshot
Approximate counting with uniform constant depth circuits
inferredcites →https://doi.org/10.1109/ccc.2005.16openalex-snapshot
On Constructing Parallel Pseudorandom Generators from One-Way Functions
inferredcites →https://doi.org/10.1109/ccc.2005.17openalex-snapshot
On the Complexity of Hardness Amplification
inferredcites →https://doi.org/10.1109/ccc.2007.15openalex-snapshot
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols
inferredcites →https://doi.org/10.1109/ccc.2007.16openalex-snapshot
On Approximate Majority and Probabilistic Time
inferredcites →https://doi.org/10.1109/ccc.2008.17openalex-snapshot
Hardness Amplification within NP against Deterministic Algorithms
inferredcites →https://doi.org/10.1109/focs.2006.13openalex-snapshot
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
inferredcites →https://doi.org/10.1109/sfcs.1982.95openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.2003.1238205openalex-snapshot
On Worst‐Case to Average‐Case Reductions for NP Problems
inferredcites →https://doi.org/10.1137/050640941openalex-snapshot
Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
inferredcites →https://doi.org/10.1137/080734030openalex-snapshot
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
inferredcites →https://doi.org/10.1137/s0097539705447281openalex-snapshot
Using Nondeterminism to Amplify Hardness
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1145/1059513.1059516openalex-snapshot
Simple extractors for all min-entropies and a new pseudorandom generator
inferredcites →https://doi.org/10.1145/1060590.1060595openalex-snapshot
On uniform amplification of hardness in NP
inferredcites →https://doi.org/10.1145/1250790.1250855openalex-snapshot
Verifying and decoding in constant depth
inferredcites →https://doi.org/10.1145/1374376.1374460openalex-snapshot
Uniform direct product theorems
inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot
P = BPP if E requires exponential circuits
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.1145/502090.502099openalex-snapshot
Extractors and pseudorandom generators
inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot
A hard-core predicate for all one-way functions
inferredcites →https://doi.org/10.1145/972639.972643openalex-snapshot
Number-theoretic constructions of efficient pseudo-random functions
inferredcites →https://doi.org/10.1561/0400000033openalex-snapshot
On the Power of Small-Depth Computation
inferredcites →https://doi.org/10.4230/lipics.approx-random.2018.58openalex-snapshot
Erasures vs. Errors in Local Decoding and Property Testing
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_6openalex-snapshot
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
inferred← citeshttps://doi.org/10.1007/978-3-030-90453-1_15openalex-snapshot
On Derandomizing Yao’s Weak-to-Strong OWF Construction
inferred← citeshttps://doi.org/10.1007/978-3-031-15982-4_4openalex-snapshot
Lower Bound on SNARGs in the Random Oracle Model
inferred← citeshttps://doi.org/10.1007/978-3-319-77404-6_24openalex-snapshot
An Average-Case Lower Bound Against $$\mathsf {ACC}^0$$
inferred← citeshttps://doi.org/10.1007/978-3-319-78372-7_12openalex-snapshot
On the Complexity of Simulating Auxiliary Input
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_36openalex-snapshot
The Complexity of Local List Decoding
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_37openalex-snapshot
Limitations of Hardness vs. Randomness under Uniform Reductions
inferred← citeshttps://doi.org/10.1007/978-3-642-01001-9_4openalex-snapshot
On the Security Loss in Cryptographic Reductions
inferred← citeshttps://doi.org/10.1007/978-3-642-03356-8_21openalex-snapshot
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_49openalex-snapshot
A PCP Characterization of AM
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_32openalex-snapshot
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_58openalex-snapshot
Query Complexity in Errorless Hardness Amplification
inferred← citeshttps://doi.org/10.1007/s00037-011-0003-7openalex-snapshot
Complexity of Hard-Core Set Proofs
inferred← citeshttps://doi.org/10.1007/s00037-013-0076-6openalex-snapshot
Randomness Buys Depth for Approximate Counting
inferred← citeshttps://doi.org/10.1007/s00037-015-0117-4openalex-snapshot
Query Complexity in Errorless Hardness Amplification
inferred← citeshttps://doi.org/10.1007/s00037-016-0128-9openalex-snapshot
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions
inferred← citeshttps://doi.org/10.1007/s00037-023-00238-9openalex-snapshot
Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
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/s00493-014-3078-3openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.04.006openalex-snapshot
AC0∘MOD2 lower bounds for the Boolean Inner Product
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.10.040openalex-snapshot
Cryptographic hardness under projections for time-bounded Kolmogorov complexity
inferred← citeshttps://doi.org/10.1109/focs.2009.62openalex-snapshot
A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
inferred← citeshttps://doi.org/10.1109/focs.2013.84openalex-snapshot
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
inferred← citeshttps://doi.org/10.1109/focs.2018.00094openalex-snapshot
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs
inferred← citeshttps://doi.org/10.1109/focs.2019.00079openalex-snapshot
Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00009openalex-snapshot
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00014openalex-snapshot
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00106openalex-snapshot
Tight Space Complexity of the Coin Problem
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00067openalex-snapshot
On the Range Avoidance Problem for Circuits
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00092openalex-snapshot
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
inferred← citeshttps://doi.org/10.1137/090766619openalex-snapshot
Bit-Probe Lower Bounds for Succinct Data Structures
inferred← citeshttps://doi.org/10.1137/1.9781611973105.46openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1137/130938219openalex-snapshot
Natural Proofs versus Derandomization
inferred← citeshttps://doi.org/10.1137/19m1276467openalex-snapshot
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
inferred← citeshttps://doi.org/10.1137/20m1321231openalex-snapshot
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits
inferred← citeshttps://doi.org/10.1137/20m1364886openalex-snapshot
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
inferred← citeshttps://doi.org/10.1145/1536414.1536480openalex-snapshot
Bit-probe lower bounds for succinct data structures
inferred← citeshttps://doi.org/10.1145/2090236.2090273openalex-snapshot
On beating the hybrid argument
inferred← citeshttps://doi.org/10.1145/2422436.2422480openalex-snapshot
On the power of nonuniformity in proofs of security
inferred← citeshttps://doi.org/10.1145/2488608.2488612openalex-snapshot
Natural proofs versus derandomization
inferred← citeshttps://doi.org/10.1145/2591796.2591846openalex-snapshot
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits
inferred← citeshttps://doi.org/10.1145/2676659openalex-snapshot
Advice Lower Bounds for the Dense Model Theorem
inferred← citeshttps://doi.org/10.1145/3018057openalex-snapshot
Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits
inferred← citeshttps://doi.org/10.1145/3313276.3316339openalex-snapshot
A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem
inferred← citeshttps://doi.org/10.1145/3322815openalex-snapshot
Constant-Error Pseudorandomness Proofs from Hardness Require Majority
inferred← citeshttps://doi.org/10.1145/3357713.3384279openalex-snapshot
Strong average-case lower bounds from non-trivial derandomization
inferred← citeshttps://doi.org/10.1145/3357713.3384328openalex-snapshot
A robust version of Hegedus’s lemma, with applications
inferred← citeshttps://doi.org/10.1145/3470860openalex-snapshot
Improved Bounds on Fourier Entropy and Min-entropy
inferred← citeshttps://doi.org/10.1145/3564246.3585189openalex-snapshot
Hardness Self-Amplification: Simplified, Optimized, and Unified
inferred← citeshttps://doi.org/10.1145/3564246.3585216openalex-snapshot
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
inferred← citeshttps://doi.org/10.1145/3564246.3585238openalex-snapshot
Optimal Explicit Small-Depth Formulas for the Coin Problem
inferred← citeshttps://doi.org/10.1145/3618260.3649603openalex-snapshot
An Efficient Quantum Parallel Repetition Theorem and Applications
inferred← citeshttps://doi.org/10.1145/3798129.3800838openalex-snapshot
Hardness Amplification beyond Boolean Functions
inferred← citeshttps://doi.org/10.1561/9781601983015openalex-snapshot
On the Power of Small-Depth Computation
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2014.618openalex-snapshot
Two Sides of the Coin Problem
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.9openalex-snapshot
Pseudorandomness When the Odds are Against You
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2020.45openalex-snapshot
Improved Bounds on Fourier Entropy and Min-Entropy
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.1902.02428openalex-snapshot
Fourier bounds and pseudorandom generators for product tests
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
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.