Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Pages 1058 - 1066
Abstract
The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C:0,1^n -> 0,1^l with stretch l>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit lower bounds, Ren, Santhanam, and Wang (FOCS’22) established a framework to design FP^NP algorithms for C-Avoid via slightly non-trivial data structures related to C. However, a major drawback of their approach is the lack of unconditional results even for C=AC^0.
In this work, we present the first unconditional FP^NP algorithm for ACC^0-Avoid. Indeed, we obtain FP^NP algorithms for the following stronger problems:
(ACC^0-RemotePoint). Given C:0,1^n -> 0,1^l for some l=quasipoly(n) such that each output bit of C is computed by a quasipoly(n)-size AC^0[m] circuit, we can find some y ∈0,1^l in FP^NP such that for every x ∈0, 1^n, the relative Hamming distance between y and C(x) is at least 1/2-1/poly(n). This problem is the ”average-case” analogue of ACC^0-Avoid.
(ACC^0-AvgPartialHard). Given x_1,…,x_l ∈0,1^n for some l=quasipoly(n), we can compute l bits y_1,…,y_l ∈0,1 in FP^NP such that for every 2^logc(n)-size ACC^0 circuit C, Pr_i[C(x_i)≠y_i]≥1/2-1/poly(n), where c=O(1). This problem generalises the strong average-case circuit lower bounds against ACC^0 in a different way.
Our algorithms can be seen as natural generalisations of the best known almost-everywhere average-case lower bounds against ACC^0 circuits by Chen, Lyu, and Williams (FOCS’20). Note that both problems above have been studied prior to our work, and no FP^NP algorithm was known even for weak circuit classes such as GF(2)-linear circuits and DNF formulas.
Our results follow from a strengthened algorithmic method: slightly non-trivial algorithms for the Satisfying-Pairs problem for C implies FP^NP algorithms for C-Avoid (as well as C-RemotePoint and C-AvgPartialHard). Here, given C-circuits C_i and inputs x_j, the C-Satisfying-Pairs problem asks to (approximately) count the number of pairs (i,j) such that C_i(x_j)=1.
A technical contribution of this work is a construction of a short, smooth, and rectangular PCP of Proximity that combines two previous PCP constructions, which may be of independent interest. It serves as a key tool that allows us to generalise the framework for Avoid to the average-case scenarios.
References
[1]
Amir Abboud, R. Ryan Williams, and Huacheng Yu. 2015. More Applications of the Polynomial Method to Algorithm Design. In SODA. SIAM, 218–230. https://doi.org/10.1137/1.9781611973730.17
[2]
Miklós Ajtai. 1983. Σ _1^1-Formulae on finite structures. Ann. Pure Appl. Log., 24, 1 (1983), 1–48. https://doi.org/10.1016/0168-0072(83)90038-6
[3]
Eric Allender and Vivek Gore. 1991. On Strong Separations from AC^ 0 (Extended Abstract). In Fundamentals of Computation Theory, 8th International Symposium, FCT ’91, Gosen, Germany, September 9-13, 1991, Proceedings, Lothar Budach (Ed.) (Lecture Notes in Computer Science, Vol. 529). Springer, 1–15. https://doi.org/10.1007/3-540-54458-5_44
[4]
Josh Alman, Timothy M. Chan, and R. Ryan Williams. 2016. Polynomial Representations of Threshold Functions and Algorithmic Applications. In FOCS. IEEE Computer Society, 467–476. https://doi.org/10.1109/FOCS.2016.57
[5]
Josh Alman, Timothy M. Chan, and R. Ryan Williams. 2020. Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. In SODA. SIAM, 637–649. https://doi.org/10.1137/1.9781611975994.39
[6]
Josh Alman and Lijie Chen. 2019. Efficient Construction of Rigid Matrices Using an Oracle. In FOCS. IEEE Computer Society, 1034–1055. https://doi.org/10.1109/FOCS.2019.00067
[7]
Josh Alman and R. Ryan Williams. 2015. Probabilistic Polynomials and Hamming Nearest Neighbors. In FOCS. IEEE Computer Society, 136–150. https://doi.org/10.1109/FOCS.2015.18
[8]
Josh Alman and R. Ryan Williams. 2017. Probabilistic rank and matrix rigidity. In STOC. ACM, 641–652. https://doi.org/10.1145/3055399.3055484
[9]
Noga Alon, Rina Panigrahy, and Sergey Yekhanin. 2009. Deterministic Approximation Algorithms for the Nearest Codeword Problem. In APPROX-RANDOM (Lecture Notes in Computer Science, Vol. 5687). Springer, 339–351. https://doi.org/10.1007/978-3-642-03685-9_26
[10]
Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264
[11]
Vikraman Arvind and Srikanth Srinivasan. 2010. Circuit Lower Bounds, Help Functions, and the Remote Point Problem. In ICS. Tsinghua University Press, 383–396. http://conference.iiis.tsinghua.edu.cn/ICS2010/content/papers/30.html
[12]
Richard Beigel and Jun Tarui. 1994. On. Comput. Complex., 4 (1994), 350–366. https://doi.org/10.1007/BF01263423
[13]
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. 2006. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput., 36, 4 (2006), 889–974. https://doi.org/10.1137/S0097539705446810
[14]
Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal. 2020. Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. In FOCS. IEEE, 858–869. https://doi.org/10.1109/FOCS46700.2020.00084
[15]
Timothy M. Chan and R. Ryan Williams. 2021. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms, 17, 1 (2021), 2:1–2:14. https://doi.org/10.1145/3402926
[16]
Eshan Chattopadhyay and David Zuckerman. 2019. Explicit two-source extractors and resilient functions. Annals of Mathematics, 189, 3 (2019), 653–705. https://doi.org/10.4007/annals.2019.189.3.1
[17]
Lijie Chen. 2019. Non-deterministic Quasi-Polynomial Time is Average-Case Hard for Circuits. In FOCS. IEEE Computer Society, 1281–1304. https://doi.org/10.1109/FOCS.2019.00079
[18]
Lijie Chen. 2022. Better Hardness via Algorithms, and New Forms of Hardness versus Randomness. Ph. D. Dissertation. Massachusetts Institute of Technology.
[19]
Lijie Chen, Ce Jin, and R. Ryan Williams. 2020. Sharp threshold results for computational complexity. In STOC. ACM, 1335–1348. https://doi.org/10.1145/3357713.3384283
[20]
Lijie Chen and Xin Lyu. 2021. Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. In STOC. ACM, 761–771. https://doi.org/10.1145/3406325.3451132
[21]
Lijie Chen, Xin Lyu, and R. Ryan Williams. 2020. Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. In FOCS. IEEE, 1–12. https://doi.org/10.1109/FOCS46700.2020.00009
[22]
Lijie Chen and Hanlin Ren. 2022. Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization. SIAM J. Comput., 51, 3 (2022), STOC20–115–STOC20–173. https://doi.org/10.1137/20M1364886
[23]
Lijie Chen and Ruosong Wang. 2019. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. In ITCS (LIPIcs, Vol. 124). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 23:1–23:20. https://doi.org/10.4230/LIPIcs.ITCS.2019.23
[24]
Lijie Chen and R. Ryan Williams. 2019. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. In CCC (LIPIcs, Vol. 137). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 19:1–19:43. https://doi.org/10.4230/LIPIcs.CCC.2019.19
[25]
Ruiwen Chen, Igor Carboni Oliveira, and Rahul Santhanam. 2018. An Average-Case Lower Bound Against ^0. In LATIN (Lecture Notes in Computer Science, Vol. 10807). Springer, 317–330. https://doi.org/10.1007/978-3-319-77404-6_24
[26]
Don Coppersmith. 1982. Rapid Multiplication of Rectangular Matrices. SIAM J. Comput., 11, 3 (1982), 467–471. https://doi.org/10.1137/0211037
[27]
Paul Erdős. 1959. Graph theory and probability. Canadian Journal of Mathematics, 11 (1959), 34–38. https://doi.org/10.4153/CJM-1959-003-9
[28]
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. 2016. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. In FOCS. IEEE Computer Society, 89–98. https://doi.org/10.1109/FOCS.2016.19
[29]
Merrick L. Furst, James B. Saxe, and Michael Sipser. 1984. Parity, Circuits, and the Polynomial-Time Hierarchy. Math. Syst. Theory, 17, 1 (1984), 13–27. https://doi.org/10.1007/BF01744431
[30]
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. 2023. Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR, https://doi.org/10.48550/arXiv.2303.05044
[31]
Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. 2007. Verifying and decoding in constant depth. In STOC. ACM, 440–449. https://doi.org/10.1145/1250790.1250855
[32]
Venkatesan Guruswami, Xin Lyu, and Xiuhan Wang. 2022. Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. In APPROX/RANDOM (LIPIcs, Vol. 245). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 20:1–20:21. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.20
[33]
Dan Gutfreund and Guy N. Rothblum. 2008. The Complexity of Local List Decoding. In APPROX-RANDOM (Lecture Notes in Computer Science, Vol. 5171). Springer, 455–468. https://doi.org/10.1007/978-3-540-85363-3_36
[34]
Johan Håstad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Adv. Comput. Res., 5 (1989), 143–170.
[35]
Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. 2021. Total Functions in the Polynomial Hierarchy. In ITCS (LIPIcs, Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 44:1–44:18. https://doi.org/10.4230/LIPIcs.ITCS.2021.44
[36]
Oliver Korten. 2021. The Hardest Explicit Construction. In FOCS. IEEE, 433–444. https://doi.org/10.1109/FOCS52979.2021.00051
[37]
Jiatu Li and Tianqi Yang. 2022. 3.1n - o(n) circuit lower bounds for explicit functions. In STOC. ACM, 1180–1193. https://doi.org/10.1145/3519935.3519976
[38]
Ketan Mulmuley. 2011. On ¶ vs. and geometric complexity theory: Dedicated to Sri Ramakrishna. J. ACM, 58, 2 (2011), 5:1–5:26. https://doi.org/10.1145/1944345.1944346
[39]
Cody D. Murray and R. Ryan Williams. 2020. Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma. SIAM J. Comput., 49, 5 (2020), https://doi.org/10.1137/18M1195887
[40]
Orr Paradise. 2021. Smooth and Strong PCPs. Comput. Complex., 30, 1 (2021), 1. https://doi.org/10.1007/s00037-020-00199-3
[41]
Mihai Pǎtraşcu. 2008. Succincter. In FOCS. IEEE Computer Society, 305–313. https://doi.org/10.1109/FOCS.2008.83
[42]
Nicholas Pippenger. 1979. On Simultaneous Resource Bounds (Preliminary Version). In FOCS. IEEE Computer Society, 307–311. https://doi.org/10.1109/SFCS.1979.29
[43]
C. Ramya. 2020. Recent Progress on Matrix Rigidity - A Survey. CoRR, abs/2009.09460 (2020).
[44]
Alexander A Razborov. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41, 4 (1987), 333–338. https://doi.org/10.1007/BF01137685
[45]
Hanlin Ren, Rahul Santhanam, and Zhikun Wang. 2022. On the Range Avoidance Problem for Circuits. In FOCS. IEEE, 640–650.
[46]
Claude E. Shannon. 1949. The synthesis of two-terminal switching circuits. Bell System technical journal, 28, 1 (1949), 59–98. https://doi.org/10.1002/j.1538-7305.1949.tb03624.x
[47]
Roman Smolensky. 1987. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In STOC. ACM, 77–82. https://doi.org/10.1145/28395.28404
[48]
Roman Smolensky. 1993. On Representations by Low-Degree Polynomials. In FOCS. IEEE Computer Society, 130–138. https://doi.org/10.1109/SFCS.1993.366874
[49]
Leslie G. Valiant. 1977. Graph-Theoretic Arguments in Low-Level Complexity. In MFCS (Lecture Notes in Computer Science, Vol. 53). Springer, 162–176. https://doi.org/10.1007/3-540-08353-7_135
[50]
R. Ryan Williams. 2013. Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput., 42, 3 (2013), 1218–1244. https://doi.org/10.1137/10080703X
[51]
R. Ryan Williams. 2014. Nonuniform Circuit Lower Bounds. J. ACM, 61, 1 (2014), 2:1–2:32. https://doi.org/10.1145/2559903
[52]
R. Ryan Williams. 2014. The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). In FSTTCS (LIPIcs, Vol. 29). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 47–60. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.47
[53]
R. Ryan Williams. 2018. Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput., 47, 5 (2018), 1965–1985. https://doi.org/10.1137/15M1024524
[54]
R. Ryan Williams. 2018. New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. Theory Comput., 14, 1 (2018), 1–25. https://doi.org/10.4086/toc.2018.v014a017
[55]
Andrew Chi-Chih Yao. 1985. Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version). In FOCS. IEEE Computer Society, 1–10. https://doi.org/10.1109/SFCS.1985.49
Index Terms
- Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Recommendations
Symmetric Exponential Time Requires Near-Maximum Circuit Size
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of ComputingWe show that there is a language in S2E/1 (symmetric exponential time with one bit of advice) with circuit complexity at least 2n/n. In particular, the above also implies the same near-maximum circuit lower bounds for the classes Σ2E, (Σ2E∩Π2E)/1, and ...
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of ComputingA recent line of research has introduced a systematic approach to exploring the complexity of explicit construction problems through the use of meta-problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. ). ...
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)-size witness circuit: a witness for x that can ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
1926 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 June 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 180Total Downloads
- Downloads (Last 12 months)72
- Downloads (Last 6 weeks)6
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in