The following pages link to Natural proofs (Q5890841):
Displaying 19 items.
- Binary pattern tile set synthesis is NP-hard (Q527409) (← links)
- Almost-natural proofs (Q716305) (← links)
- Models of lower-bounds proofs (Q1107322) (← links)
- Optimal bounds for the approximation of Boolean functions and some applications (Q1390872) (← links)
- Lower bounds for unrestricted Boolean circuits: open problems (Q1625135) (← links)
- Exploring crypto dark matter: new simple PRF candidates and their applications (Q1631360) (← links)
- On the limits of gate elimination (Q1635510) (← links)
- The hunting of the SNARK (Q1698394) (← links)
- The correlation between parity and quadratic polynomials mod \(3\) (Q1881261) (← links)
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\) (Q2139645) (← links)
- Circuit lower bounds à la Kolmogorov (Q2508341) (← links)
- Natural proofs versus derandomization (Q2805512) (← links)
- Barriers for Rank Methods in Arithmetic Complexity (Q4993264) (← links)
- Small bias requires large formulas (Q5002692) (← links)
- Pseudorandom Functions: Three Decades Later (Q5021131) (← links)
- Natural proofs (Q5906823) (← links)
- Circuit complexity before the dawn of the new millennium (Q6567750) (← links)
- One-tape Turing machine and branching program lower bounds for MCSP (Q6614616) (← links)
- Structural lower bounds on black-box constructions of pseudorandom functions (Q6652977) (← links)
