Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
\(\Sigma_ 1^ 1\)-formulae on finite structures
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
On ACC
Smooth and strong PCPs
An average-case lower bound against \(\mathsf{ACC}^0\)
Explicit two-source extractors and resilient functions
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
On P vs. NP and geometric complexity theory
The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets
Nonuniform ACC Circuit Lower Bounds
Graph Theory and Probability
Parity, circuits, and the polynomial-time hierarchy
The Complexity of Local List Decoding
Deterministic Approximation Algorithms for the Nearest Codeword Problem
Rapid Multiplication of Rectangular Matrices
Faster All-Pairs Shortest Paths via Circuit Complexity
New algorithms and lower bounds for circuits with linear threshold gates
Probabilistic rank and matrix rigidity
Deterministic APSP, Orthogonal Vectors, and More
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
Sharp threshold results for computational complexity
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
Computational Complexity
More Applications of the Polynomial Method to Algorithm Design
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Efficient Construction of Rigid Matrices Using an NP Oracle
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma

This page was built for publication: Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms