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

DOI10.1145/3564246.3585147MaRDI QIDQ6499284zbMATH OpenFDO

Authors Yeyuan Chen, Yi-Zhi Huang, Hanlin Ren

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585147

zbMATH Keywords

circuit complexityexplicit constructionsrange avoidanceremote point problemsatisfying pairs problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• An average-case lower bound against \(\mathsf{ACC}^0\)
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• Computational Complexity
• Deterministic Approximation Algorithms for the Nearest Codeword Problem
• Deterministic APSP, Orthogonal Vectors, and More
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Explicit two-source extractors and resilient functions
• Faster all-pairs shortest paths via circuit complexity
• Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
• Graph Theory and Probability
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1346528 (Why is no real title available?)
• Improving exhaustive search implies superpolynomial lower bounds
• Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• More applications of the polynomial method to algorithm design
• Nonuniform ACC circuit lower bounds
• On ACC
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• Parity, circuits, and the polynomial-time hierarchy
• Probabilistic rank and matrix rigidity
• Rapid Multiplication of Rectangular Matrices
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Sharp threshold results for computational complexity
• Smooth and strong PCPs
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• The Complexity of Local List Decoding
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• The remote point problem, small bias spaces, and expanding generator sets
• Verifying and decoding in constant depth

Cited in

(3)

• A technique for hardness amplification against AC^0
• Range avoidance for low-depth circuits and connections to pseudorandomness
• Oblivious complexity classes revisited: lower bounds and hierarchies

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499284)