Self-Improvement for Circuit-Analysis Problems
Pages 1374 - 1385
Abstract
Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a “self-improving” (or “bootstrapping”) theorem for Circuit-SAT, #Circuit-SAT, and its fully-quantified version: solving one of these problems faster for “large” circuit sizes implies a significant speed-up for “smaller” circuit sizes. Our general arguments work for a variety of models solving circuit-analysis problems, including non-uniform circuits and randomized models of computation.
We derive striking consequences for the complexities of these problems, in both the fine-grained and parameterized setting. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply subexponential-time algorithms for Circuit-SAT on 2o(n)-size circuits, refuting the Exponential Time Hypothesis. We also show that any algorithm for Circuit-SAT with k inputs and n gates running in 1000000k + n1+ε time (for all ε > 0) would imply algorithms running in time (1+ε)k + n1+ε time (for all ε > 0), also refuting the Exponential Time Hypothesis. Applying our ideas in the #Circuit-SAT setting, we prove new unconditional lower bounds against uniform circuits with symmetric gates for functions in deterministic linear time.
References
[1]
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. 2016. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In STOC. ACM, 375–388. https://doi.org/10.1145/2897518.2897653
[2]
Amir Abboud, Ryan Williams, and Huacheng Yu. 2015. More applications of the polynomial method to algorithm design. In SODA. 218–230.
[3]
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. 2018. Bootstrapping variables in algebraic circuits. In STOC. ACM, 1166–1179. https://doi.org/10.1145/3188745.3188762
[4]
Eric Allender, Jin-Yi Cai, Lance Fortnow, William Gasarch, Neil Immerman, Stuart Kurtz, James Royer, and Ryan Williams. 2022. Open Problems Column: Open Problems by or Inspired by Juris Hartmanis. SIGACT News, 53, 4 (2022), 26.
[5]
Eric Allender and Vivek Gore. 1994. A Uniform Circuit Lower Bound for the Permanent. SIAM J. Comput., 23, 5 (1994), 1026–1049. https://doi.org/10.1137/S0097539792233907
[6]
Eric Allender and Michal Koucký. 2010. Amplifying lower bounds by means of self-reducibility. J. ACM, 57, 3 (2010), 14:1–14:36.
[7]
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay. 2001. Time-Space Tradeoffs in the Counting Hierarchy. In CCC. 295–302. https://doi.org/10.1109/CCC.2001.933896
[8]
Josh Alman, Timothy M. Chan, and R. Ryan Williams. 2016. Polynomial Representations of Threshold Functions and Algorithmic Applications. In FOCS. 467–476.
[9]
Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. isbn:978-0-521-42426-4
[10]
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, and Chris Umans. 2022. Fast Multivariate Multipoint Evaluation Over All Finite Fields. In FOCS. IEEE, 221–232.
[11]
Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra. 2022. Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. In STOC. ACM, 403–415.
[12]
Stephen A. Bloch, Jonathan F. Buss, and Judy Goldsmith. 1998. Sharply Bounded Alternation and Quasilinear Time. Theory Comput. Syst., 31, 2 (1998), 187–214. https://doi.org/10.1007/s002240000085
[13]
Allan Borodin and R. Moenck. 1974. Fast Modular Transforms. J. Comput. Syst. Sci., 8, 3 (1974), 366–386. https://doi.org/10.1016/S0022-0000(74)80029-2
[14]
Mark Braverman, Young Kun-Ko, and Omri Weinstein. 2015. Approximating the best Nash Equilibrium in n^ o^ (log n)-time breaks the Exponential Time Hypothesis. In SODA. 970–982. https://doi.org/10.1137/1.9781611973730.66
[15]
Jonathan F. Buss and Judy Goldsmith. 1993. Nondeterminism Within P. SIAM J. Comput., 22, 3 (1993), 560–572. https://doi.org/10.1137/0222038
[16]
Samuel R. Buss and Ryan Williams. 2015. Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex., 24, 3 (2015), 533–600. https://doi.org/10.1007/s00037-015-0104-9
[17]
Liming Cai and Jianer Chen. 1997. On the Amount of Nondeterminism and the Power of Verifying. SIAM J. Comput., 26, 3 (1997), 733–750. https://doi.org/10.1137/S0097539793258295
[18]
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. 2006. A Duality between Clause Width and Clause Density for SAT. In CCC. 252–260.
[19]
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
[20]
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. 2020. Beyond Natural Proofs: Hardness Magnification and Locality. In ITCS. 70:1–70:48. https://doi.org/10.4230/LIPIcs.ITCS.2020.70
[21]
Lijie Chen, Ce Jin, and R. Ryan Williams. 2019. Hardness Magnification for all Sparse NP Languages. In FOCS. 1240–1255.
[22]
Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. 2019. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In CCC. 30:1–30:21. https://doi.org/10.4230/LIPIcs.CCC.2019.30
[23]
Lijie Chen, Ron D. Rothblum, Roei Tell, and Eylon Yogev. 2020. On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. In FOCS. IEEE, 13–23.
[24]
James W Cooley and John W Tukey. 1965. An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 19, 90 (1965), 297–301.
[25]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. isbn:978-3-319-21274-6 https://doi.org/10.1007/978-3-319-21275-3
[26]
Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. 2016. Known Algorithms for Edge Clique Cover are Probably Optimal. SIAM J. Comput., 45, 1 (2016), 67–83. https://doi.org/10.1137/130947076
[27]
Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. 2014. Exponential Time Complexity of the Permanent and the Tutte Polynomial. ACM Trans. Algorithms, 10, 4 (2014), 21:1–21:32. https://doi.org/10.1145/2635812
[28]
Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, and Grigory Yaroslavtsev. 2010. New upper bounds on the Boolean circuit complexity of symmetric functions. Inf. Process. Lett., 110, 7 (2010), 264–267. https://doi.org/10.1016/j.ipl.2010.01.007
[29]
Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer. isbn:978-1-4612-6798-0 https://doi.org/10.1007/978-1-4612-0515-9
[30]
Charles M. Fiduccia. 1972. Polynomial Evaluation via the Division Algorithm: The Fast Fourier Transform Revisited. In STOC. 88–93.
[31]
Jörg Flum, Martin Grohe, and Mark Weyer. 2006. Bounded fixed-parameter tractability and log^ 2n nondeterministic bits. J. Comput. Syst. Sci., 72, 1 (2006), 34–71. https://doi.org/10.1016/j.jcss.2005.06.003
[32]
Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas. 2005. Time-space lower bounds for satisfiability. J. ACM, 52, 6 (2005), 835–865.
[33]
Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, and Ramprasad Saptharishi. 2023. Fast Numerical Multivariate Multipoint Evaluation. Electronic Colloquium on Computational Complexity, TR23-033 (2023).
[34]
Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. 2008. Data reduction and exact algorithms for clique cover. ACM J. Exp. Algorithmics, 13 (2008), https://doi.org/10.1145/1412228.1412236
[35]
Russell Impagliazzo and Ramamohan Paturi. 1999. Complexity of k-SAT. In CCC. 237–240. https://doi.org/10.1109/CCC.1999.766282
[36]
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63, 4 (2001), 512–530. https://doi.org/10.1006/jcss.2001.1774
[37]
Stasys Jukna. 2012. Boolean function complexity: advances and frontiers. 27, Springer Science & Business Media.
[38]
Daniel M. Kane and Ryan Williams. 2016. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In STOC. 633–643.
[39]
Ravi Kannan. 1983. Alternation and the Power of Nondeterminism. In STOC. ACM, 344–346.
[40]
Kiran S. Kedlaya and Christopher Umans. 2011. Fast Polynomial Factorization and Modular Composition. SIAM J. Comput., 40, 6 (2011), 1767–1802.
[41]
Chandra M. R. Kintala and Patrick C. Fischer. 1977. Computations with a Restricted Number of Nondeterministic Steps (Extended Abstract). In STOC. ACM, 178–185. https://doi.org/10.1145/800105.803407
[42]
Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse. 2019. Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. In SODA. SIAM, 639–646. https://doi.org/10.1137/1.9781611975482.40
[43]
Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse. 2023. Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models. Theory of Computing, 19, 12 (2023), 1–30. https://doi.org/10.4086/toc.2023.v019a012
[44]
Francois Le Gall and Florent Urrutia. 2018. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. In SODA. SIAM, 1029–1046.
[45]
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. 2003. Playing large games using simple strategies. In Proceedings 4th ACM Conference on Electronic Commerce (EC). ACM, 36–41. https://doi.org/10.1145/779928.779933
[46]
Richard J. Lipton and Ryan Williams. 2013. Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity, 22, 2 (2013), 311–343. https://doi.org/10.1007/s00037-013-0069-5
[47]
Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. 2019. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In STOC. ACM, 1215–1225.
[48]
Abhijit Mudigonda and R. Ryan Williams. 2021. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. In ITCS (LIPIcs, Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 50:1–50:20.
[49]
Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. 2019. Hardness Magnification near State-Of-The-Art Lower Bounds. In 34th Computational Complexity Conference, CCC 2019. 27:1–27:29. https://doi.org/10.4230/LIPIcs.CCC.2019.27
[50]
Igor Carboni Oliveira and Rahul Santhanam. 2018. Hardness Magnification for Natural Problems. In FOCS. 65–76.
[51]
Ojas Parekh, Cynthia A. Phillips, Conrad D. James, and James B. Aimone. 2018. Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication. In SPAA. ACM, 67–76. https://doi.org/10.1145/3210377.3210410
[52]
Ramamohan Paturi and Pavel Pudlák. 2010. On the complexity of circuit satisfiability. In STOC. ACM, 241–250.
[53]
Wolfgang J. Paul. 1976. Realizing Boolean Functions on Disjoint sets of Variables. Theor. Comput. Sci., 2, 3 (1976), 383–396. https://doi.org/10.1016/0304-3975(76)90089-X
[54]
Nicholas Pippenger and Michael J. Fischer. 1979. Relations among complexity measures. J. ACM, 26, 2 (1979), 361–381.
[55]
Aviad Rubinstein. 2016. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. In FOCS. 258–265.
[56]
András Z. Salamon and Michael Wehar. 2022. Superlinear Lower Bounds Based on ETH. In STACS (LIPIcs, Vol. 219). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 55:1–55:16. https://doi.org/10.4230/LIPIcs.STACS.2022.55
[57]
Rahul Santhanam. 2023. An Algorithmic Approach to Uniform Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC), TR23-028 (2023), 100.
[58]
Aravind Srinivasan. 2003. On the approximability of clique and related maximization problems. J. Comput. Syst. Sci., 67, 3 (2003), 633–651. https://doi.org/10.1016/S0022-0000(03)00110-7
[59]
Suguru Tamaki. 2016. A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates. Electronic Colloquium on Computational Complexity (ECCC), TR16-100 (2016), http://eccc.hpi-web.de/report/2016/100
[60]
Leslie G. Valiant. 1976. Universal Circuits (Preliminary Report). In STOC. ACM, 196–203.
[61]
Dieter van Melkebeek. 2006. A Survey of Lower Bounds for Satisfiability and Related Problems. Found. Trends Theor. Comput. Sci., 2, 3 (2006), 197–303. https://doi.org/10.1561/0400000012
[62]
Dieter van Melkebeek and Ran Raz. 2005. A time lower bound for satisfiability. Theor. Comput. Sci., 348, 2-3 (2005), 311–320. https://doi.org/10.1016/j.tcs.2005.09.020
[63]
Dieter van Melkebeek and Thomas Watson. 2012. Time-Space Efficient Simulations of Quantum Computations. Theory Comput., 8, 1 (2012), 1–51. https://doi.org/10.4086/toc.2012.v008a001
[64]
Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM). 3447–3487.
[65]
Heribert Vollmer. 1999. Introduction to Circuit Complexity - A Uniform Approach. Springer. isbn:978-3-540-64310-4 https://doi.org/10.1007/978-3-662-03927-4
[66]
Ryan Williams. 2013. Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput., 42, 3 (2013), 1218–1244. https://doi.org/10.1137/10080703X
[67]
Ryan Williams. 2014. Nonuniform ACC circuit lower bounds. J. ACM, 61, 1 (2014), 2.
[68]
Ryan Williams. 2023. Self-Improvement for Circuit-Analysis Problems. Electron. Colloquium Comput. Complex., TR23-082 (2023), ECCC:TR23-082. https://eccc.weizmann.ac.il/report/2023/082
[69]
R. Ryan Williams. 2018. New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. Theory of Computing, 14, 1 (2018), 1–25.
[70]
Or Zamir. 2023. Algorithmic Applications of Hypergraph and Partition Containers. In STOC. ACM, 985–998. https://doi.org/10.1145/3564246.3585163
Index Terms
- Self-Improvement for Circuit-Analysis Problems
Recommendations
Derandomizing polynomial identity tests means proving circuit lower bounds
We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, ...
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are ...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThe Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
2049 pages
ISBN:9798400703836
DOI:10.1145/3618260
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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: 11 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation
Conference
STOC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 299Total Downloads
- Downloads (Last 12 months)299
- Downloads (Last 6 weeks)58
Reflects downloads up to 17 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in