Hardness of range avoidance and proof complexity generators from demi-bits
From MaRDI portal
Cites work
- A proof complexity conjecture and the incompleteness theorem
- A proof complexity generator
- Approximate counting in bounded arithmetic
- Automating algebraic proof systems is NP-hard
- Average-Case Complexity
- Bounded arithmetic and the polynomial hierarchy
- Circuit lower bounds in bounded arithmetics
- Clique is hard on average for unary Sherali-Adams
- Computational Complexity
- Derandomizing Arthur-Merlin games using hitting sets
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Fragments of approximate counting
- Graph colouring is hard on average for polynomial calculus and Nullstellensatz
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- Hardness vs randomness, revised: uniform, non-black-box, and instance-wise
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (Why is no real title available?)
- scientific article; zbMATH DE number 806744 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Indistinguishability obfuscation from well-founded assumptions
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Large clique is hard on average for resolution
- Learning algorithms versus automatability of Frege systems
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Logical foundations of proof complexity
- Lower bounds for the polynomial calculus
- Nisan-Wigderson generators in proof complexity: new lower bounds
- Nisan-Wigderson generators in proof systems with forms of interpolation
- Non-black-box worst-case to average-case reductions within NP
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- On the hardness of permanent
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- On the range avoidance problem for circuits
- On the weak pigeonhole principle
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Probabilistic encryption
- Proof Complexity
- Proof complexity generators
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Pseudorandom Generators in Propositional Proof Complexity
- Pseudorandomness for approximate counting and sampling
- Random-Self-Reducibility of Complete Sets
- Range avoidance and the complexity of explicit constructions
- Range avoidance for constant depth circuits: hardness and algorithms
- Range avoidance for low-depth circuits and connections to pseudorandomness
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
- Resolution lower bounds for perfect matching principles
- Resolution over linear equations modulo two
- Reverse mathematics of complexity lower bounds
- Simple extractors for all min-entropies and a new pseudorandom generator
- Small circuits and dual weak PHP in the universal theory of p-time algorithms
- Stretching demi-bits and nondeterministic-secure pseudorandomness
- Strong vs. weak range avoidance and the linear ordering principle
- Tautologies from pseudo-random generators
- The hardest explicit construction
- The relative efficiency of propositional proof systems
- The strength of sharply bounded induction
- Total functions in the polynomial hierarchy
- Why are proof complexity lower bounds hard?
This page was built for publication: Hardness of range avoidance and proof complexity generators from demi-bits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445643)