The following pages link to Natural proofs (Q5906823):
Displaying 50 items.
- Kolmogorov width of discrete linear spaces: an approach to matrix rigidity (Q301519) (← links)
- Physical portrayal of computational complexity (Q408483) (← links)
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Exponential lower bound for bounded depth circuits with few threshold gates (Q413295) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
- Limits on alternation trading proofs for time-space lower bounds (Q496301) (← links)
- The communication complexity of addition (Q519955) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- On matrix rigidity and locally self-correctable codes (Q645122) (← links)
- The complexity of explicit constructions (Q693069) (← links)
- Almost-natural proofs (Q716305) (← links)
- Independence results for variants of sharply bounded induction (Q716498) (← links)
- Substitutions into propositional tautologies (Q845921) (← links)
- Turing machines and bimachines (Q930927) (← links)
- Resource-bounded measure on probabilistic classes (Q963376) (← links)
- Synthesizers and their application to the parallel construction of pseudo-random functions (Q1288205) (← links)
- Expressive power of SQL. (Q1401278) (← links)
- Almost \(k\)-wise independence and hard Boolean functions. (Q1401305) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits (Q1567407) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Adaptively secure distributed PRFs from LWE (Q1631339) (← links)
- Proofs of Work from worst-case assumptions (Q1673424) (← links)
- Lower bounds for invariant queries in logics with counting. (Q1853505) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\) (Q2009642) (← links)
- Adaptively secure distributed PRFs from \(\mathsf{LWE}\) (Q2043324) (← links)
- A \#SAT algorithm for small constant-depth circuits with PTF gates (Q2118395) (← links)
- Expander-based cryptography meets natural proofs (Q2125080) (← links)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
- On the complexity of matrix rank and rigidity (Q2268340) (← links)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (Q2281256) (← links)
- Polynomial time ultrapowers and the consistency of circuit lower bounds (Q2288334) (← links)
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression (Q2316930) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- Lower bounds for the circuit size of partially homogeneous polynomials (Q2405138) (← links)
- Zero knowledge and circuit minimization (Q2407082) (← links)
- Robust simulations and significant separations (Q2407096) (← links)
- Block-symmetric polynomials correlate with parity better than symmetric (Q2410677) (← links)
- Extremal properties of polynomial threshold functions (Q2475403) (← links)
- Quantum certificate complexity (Q2475404) (← links)
- Using the renormalization group to classify Boolean functions (Q2482277) (← links)
- On converting CNF to DNF (Q2576880) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- Minimizing nfa's and regular expressions (Q2641868) (← links)
- Tautologies from Pseudo-Random Generators (Q2736584) (← links)
- Natural Proofs versus Derandomization (Q2805512) (← links)
