Range avoidance and remote point: new algorithms and hardness
From MaRDI portal
Cites work
- A Depth-Universal Circuit
- Almost-everywhere circuit lower bounds from non-trivial derandomization
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Computational Complexity
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Explicit directional affine extractors and improved hardness for linear branching programs
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness against linear branching programs and more
- scientific article; zbMATH DE number 3167429 (Why is no real title available?)
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- scientific article; zbMATH DE number 65749 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- Indistinguishability obfuscation from well-founded assumptions
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- List Decoding of Binary Codes–A Brief Survey of Some Recent Results
- Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
- Nonuniform ACC circuit lower bounds
- On oracles and algorithmic methods for proving lower bounds
- On the complexity of k-SAT
- On the range avoidance problem for circuits
- Pseudorandomness
- 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
- Some remarks on the theory of graphs
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Super-polynomial versus half-exponential circuit size in the exponential hierarchy
- The hardest explicit construction
- Total functions in the polynomial hierarchy
- Which problems have strongly exponential complexity?
This page was built for publication: Range avoidance and remote point: new algorithms and hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445606)