Quantified derandomization of linear threshold circuits. (English) Zbl 1428.68169
Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 855-865 (2018).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q06 | Networks and circuits as models of computation; circuit complexity |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68W20 | Randomized algorithms |
Citations:
Zbl 1275.68071References:
| [1] | Scott Aaronson. 2017. |
| [2] | P ? = N P. Accessed at http://www.scottaaronson.com/ papers/pnp.pdf, June 20, 2017. |
| [3] | Miklos Ajtai and Avi Wigderson. 1985. Deterministic simulation of probabilistic constant depth circuits. In Proc. 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 10.1109/SFCS.1985.19 |
| [4] | Eric Allender and Michal Koucký. 2010. Amplifying lower bounds by means of self-reducibility. Journal of the ACM 57, 3 (2010), 14, 36. 10.1145/1706591.1706594 · Zbl 1327.68112 |
| [5] | N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth. 1992. |
| [6] | Construction of Asymptotically Good Low-rate Error-correcting Codes Through Pseudo-random Graphs. IEEE Transactions on Information Theory 38, 2 (1992), 509-516. 10.1109/18.119713 · Zbl 0744.94023 |
| [7] | Kazuyuki Amano and Atsushi Saito. 2015. |
| [8] | Sanjeev Arora and Boaz Barak. 2009. |
| [9] | Computational complexity: A modern approach. Cambridge University Press, Cambridge. · Zbl 1193.68112 |
| [10] | Z. Bar-Yossef, O. Reingold, R. Shaltiel, and L. Trevisan. 2002. Streaming computation of combinatorial objects. In Proc. 17th Annual IEEE Conference on Computational Complexity (CCC). 133-142. |
| [11] | Paul Beame, Erik Brisson, and Richard Ladner. 1992. The complexity of computing symmetric functions using threshold circuits. Theoretical Computer Science 100, 1 (1992), 253-265. 10.1016/0304-3975(92)90372-M · Zbl 0780.68052 |
| [12] | Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. 2012. Approximating AC 0 by small height decision trees and a deterministic algorithm for #AC 0 SAT. In Proc. 27th Annual IEEE Conference on Computational Complexity (CCC). 117- 125. 10.1109/CCC.2012.40 |
| [13] | Eli Ben-Sasson and Emanuele Viola. 2014. Short PCPs with projection queries. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP). 163-173. · Zbl 1410.68135 |
| [14] | Manuel Blum and Silvio Micali. 1984. How to Generate Cryptographically Strong Sequences of Pseudo-random Bits. SIAM Journal of Computing 13, 4 (1984), 850-864. 10.1137/0213053 · Zbl 0547.68046 |
| [15] | Mark Braverman. 2010. Polylogarithmic independence fools AC 0 circuits. Journal of the ACM 57, 5 (2010). 10.1145/1754399.1754401 · Zbl 1327.68108 |
| [16] | Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. 2015. Mining circuit lower bound proofs for meta-algorithms. Computational Complexity 24, 2 (2015), 333-392. 10.1007/s00037-015-0100-0 · Zbl 1401.68116 |
| [17] | Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. 2016. Average-case lower bounds and satisfiability algorithms for small threshold circuits. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC). 1:1-1:35. 10.4230/LIPIcs.CCC.2016.1 · Zbl 1380.68191 |
| [18] | Kuan Cheng and Xin Li. 2016. Randomness Extraction in AC0 and with Small Locality. Electronic Colloquium on Computational Complexity: ECCC 23 (2016), 18. · Zbl 1522.68738 |
| [19] | Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola. 2010. Bounded independence fools halfspaces. SIAM Journal of Computing 39, 8 (2010), 3441-3462. 10.1137/100783030 · Zbl 1221.68169 |
| [20] | Devdatt Dubhashi and Alessandro Panconesi. 2009. |
| [21] | Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press. · Zbl 1213.60006 |
| [22] | Quantified Derandomization of Linear Threshold Circuits STOC’18, June 25-29, 2018, Los Angeles, CA, USA · Zbl 1428.68169 |
| [23] | Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola. 2013. |
| [24] | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Transactions on Information Theory 59, 10 (2013), 6611-6627. 10.1109/TIT.2013.2270275 · Zbl 1364.94780 |
| [25] | Oded Goldreich. 2008. |
| [26] | Computational Complexity: A Conceptual Perspective. Cambridge University Press, New York, NY, USA. · Zbl 1154.68056 |
| [27] | Oded Goldreich, Emanuele Viola, and Avi Wigderson. 2015. |
| [28] | On Randomness Extraction in AC0. In Proc. 30th Annual IEEE Conference on Computational Complexity (CCC). 601-668. 10.4230/LIPIcs.CCC.2015.601 · Zbl 1388.68074 |
| [29] | Oded Goldreich and Avi Widgerson. 2013. On derandomizing algorithms that err extremely rarely. Electronic Colloquium on Computational Complexity: ECCC 20 (2013), 152. 10.1145/2591796.2591808 · Zbl 1315.68152 |
| [30] | Oded Goldreich and Avi Widgerson. 2014. On derandomizing algorithms that err extremely rarely. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC). 109-118. Full version available online at Electronic Colloquium on Computational Complexity: ECCC, 20:152 (Rev. 2), 2013. 10.1145/2591796.2591808 · Zbl 1315.68152 |
| [31] | Parikshit Gopalan, Daniel Kane, and Raghu Meka. 2015. |
| [32] | Pseudorandomness via the discrete Fourier transform. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 903-922. |
| [33] | Parikshit Gopalan, Raghu Meka, and Omer Reingold. 2013. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity 22, 2 (2013), 275-310. · Zbl 1286.68230 |
| [34] | Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman. 2010. Fooling functions of halfspaces under product distributions. In Proc. 25th Annual IEEE Conference on Computational Complexity (CCC). 223-234. 10.1109/CCC.2010.29 |
| [35] | Hans Dietmar Gröger and György” Turán. 1991. On linear decision trees computing Boolean functions. In Proc. 18th International Colloquium on Automata, Languages and Programming (ICALP). 707-718. · Zbl 0769.68044 |
| [36] | Prahladh Harsha, Adam Klivans, and Raghu Meka. 2012. An invariance principle for polytopes. Journal of the ACM 59, 6 (2012), 29:1-29:25. 10.1145/2395116.2395118 · Zbl 1281.68182 |
| [37] | Alexander D. Healy. 2008. Randomness-efficient sampling within NC 1. Computational Complexity 17, 1 (2008), 3-37. 10.1007/s00037-007-0238-5 · Zbl 1149.68027 |
| [38] | Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. 2002. In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65, 4 (2002), 672-694. 10.1016/S0022-0000(02)00024-7 · Zbl 1059.68047 |
| [39] | Russell Impagliazzo, William Matthews, and Ramamohan Paturi. 2012. A satisfiability algorithm for AC 0. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 961-972. · Zbl 1423.68583 |
| [40] | Russell Impagliazzo, Raghu Meka, and David Zuckerman. 2012. Pseudorandomness from shrinkage. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 111-119. 10.1109/FOCS.2012.78 · Zbl 1427.68096 |
| [41] | Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. 1997. Size-depth tradeoffs for threshold circuits. SIAM Journal of Computing 26, 3 (1997), 693-707. 10.1137/S0097539792282965 · Zbl 0870.68069 |
| [42] | Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider. 2013. A satisfiability algorithm for sparse depth two threshold circuits. In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 479-488. 10.1109/FOCS.2013.58 |
| [43] | R. Impagliazzo and A. Wigderson. 1998. Randomness vs. Time: De-Randomization Under a Uniform Assumption. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 734-. · Zbl 1052.68034 |
| [44] | Daniel M. Kane. 2011. A small PRG for polynomial threshold functions of Gaussians. In Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 257-266. 10.1109/FOCS.2011.16 · Zbl 1292.68112 |
| [45] | Daniel M. Kane. 2014. |
| [46] | A pseudorandom generator for polynomial threshold functions of Gaussian with subpolynomial seed length. In Proc. 29th Annual IEEE Conference on Computational Complexity (CCC). 217-228. 10.1109/CCC.2014.30 |
| [47] | 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 Proc. 48th Annual ACM Symposium on Theory of Computing (STOC). 633-643. 10.1145/2897518.2897636 · Zbl 1373.68220 |
| [48] | Zohar S. Karnin, Yuval Rabani, and Amir Shpilka. 2012. |
| [49] | Explicit dimension reduction and its applications. SIAM Journal of Computing 41, 1 (2012), 219-249. 10.1137/110828812 · Zbl 1253.68154 |
| [50] | Pravesh K. Kothari and Raghu Meka. 2015. |
| [51] | Almost optimal pseudorandom generators for spherical caps. In Proc. 47th Annual ACM Symposium on Theory of Computing (STOC). 247-256. 10.1145/2746539.2746611 · Zbl 1321.65008 |
| [52] | Nathan Linial, Yishay Mansour, and Noam Nisan. 1993. Constant depth circuits, Fourier transform, and learnability. Journal of the Association for Computing Machinery 40, 3 (1993), 607-620. 10.1145/174130.174138 · Zbl 0781.94006 |
| [53] | Raghu Meka and David Zuckerman. 2013. Pseudorandom generators for polynomial threshold functions. SIAM Journal of Computing 42, 3 (2013), 1275-1301. · Zbl 1272.68132 |
| [54] | Joseph Naor and Moni Naor. 1993. Small-bias probability spaces: efficient constructions and applications. SIAM Journal of Computing 22, 4 (1993), 838-856. 10.1137/0222053 · Zbl 0776.60014 |
| [55] | Noam Nisan. 1993. |
| [56] | The communication complexity of threshold gates. In Combinatorics, Paul Erdős is eighty, Vol. 1. 301-315. · Zbl 0790.94028 |
| [57] | Noam Nisan and Avi Wigderson. 1994. |
| [58] | Hardness vs. randomness. Journal of Computer and System Sciences 49, 2 (1994), 149-167. 10.1016/S0022-0000(05)80043-1 · Zbl 0821.68057 |
| [59] | Ryan O’Donnell. 2014. |
| [60] | Analysis of Boolean Functions. Cambridge University Press. · Zbl 1336.94096 |
| [61] | Ramamohan Paturi and Michael E. Saks. 1994. Approximating threshold circuits by rational functions. Information and Computation 112, 2 (1994), 257-272. 10.1006/inco.1994.1059 · Zbl 0820.68054 |
| [62] | Yuval Rabani and Amir Shpilka. 2010. Explicit Construction of a Small epsilon-Net for Linear Threshold Functions. SIAM Journal of Computing 39, 8 (2010), 3501-3520. 10.1137/090764190 · Zbl 1209.68347 |
| [63] | Ran Raz, Omer Reingold, and Salil Vadhan. 2002. Extracting all the randomness and reducing the error in Trevisan’s extractors. Journal of Computer and System Sciences 65, 1 (2002), 97-128. 10.1006/jcss.2002.1824 · Zbl 1020.68029 |
| [64] | V. P. Roychowdhury, A. Orlitsky, and Kai-Yeung Siu. 1994. |
| [65] | Lower bounds on threshold and related circuits via communication complexity. IEEE Transactions on Information Theory 40, 2 (1994), 467-474. 10.1109/18.312169 · Zbl 0810.94043 |
| [66] | Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. 2016. |
| [67] | Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science. · Zbl 1398.68259 |
| [68] | Rahul Santhanam. 2010. Fighting perebor: new and improved algorithms for formula and QBF satisfiability. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 183-192. 10.1109/FOCS.2010.25 |
| [69] | Rahul Santhanam and Ryan Williams. 2013. On medium-uniformity and circuit lower bounds. In Proc. 28th Annual IEEE Conference on Computational Complexity (CCC). 15-23. · Zbl 1314.68139 |
| [70] | Rocco Servedio and Li-Yang Tan. 2017. Deterministic search for CNF satisfying assignments in almost polynomial time. In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS). |
| [71] | Rocco Servedio and Li-Yang Tan. 2017. Learning and fooling depth-two threshold circuits. (2017). |
| [72] | Unpublished manuscript. · Zbl 1344.01015 |
| [73] | Rocco A. Servedio. 2007. |
| [74] | Every linear threshold function has a low-weight approximator. Computational Complexity 16, 2 (2007), 180-209. 10.1007/s00037-007-0228-7 · Zbl 1128.68043 |
| [75] | K. Seto and S. Tamaki. 2012. A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. In Proc. 27th Annual IEEE Conference on Computational Complexity (CCC). 107-116. 10.1109/CCC.2012.29 · Zbl 1286.68208 |
| [76] | Roman Smolensky. 1990. |
| [77] | Amnon Ta-Shma. 2017. Explicit, Almost Optimal, Epsilon-Balanced Codes. In Proc. 49th Annual ACM Symposium on Theory of Computing (STOC). 10.1145/3055399.3055408 · Zbl 1378.94079 |
| [78] | 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 23 (2016), 100. |
| [79] | Roei Tell. 2017. Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In Proc. 32nd Annual IEEE Conference on Computational Complexity (CCC). 18:1 - 18:49. 10.4230/LIPIcs.CCC.2017.13 · Zbl 1440.68131 |
| [80] | Roei Tell. 2017. Quantified Derandomization of Linear Threshold Circuits (rev. 2). Electronic Colloquium on Computational Complexity: ECCC 24 (2017), 145. 10.1145/3188745.3188822 · Zbl 1440.68131 |
| [81] | Luca Trevisan. 2001. Extractors and Pseudorandom Generators. Journal of the ACM 48, 4 (2001), 860-879. 10.1145/502090.502099 · Zbl 1127.68403 |
| [82] | Luca Trevisan and TongKe Xue. 2013. A derandomized switching lemma and an improved derandomization of AC0. In Proc. 28th Annual IEEE Conference on Computational Complexity (CCC). 242-247. |
| [83] | Emanuele Viola. 2005. The complexity of constructing pseudorandom generators from hard functions. Computational Complexity 13, 3-4 (2005), 147-188. 10.1007/s00037-004-0187-1 · Zbl 1061.68077 |
| [84] | Ryan Williams. 2011. |
| [85] | Non-uniform ACC circuit lower bounds. In Proc. 26th Annual IEEE Conference on Computational Complexity (CCC). 115-125. 10.1109/CCC.2011.36 |
| [86] | Ryan Williams. 2013. |
| [87] | Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM Journal of Computing 42, 3 (2013), 1218-1244. · Zbl 1275.68071 |
| [88] | Ryan Williams. 2014. Algorithms for circuits and circuits for algorithms: Connecting the tractable and intractable. In Proc. International Congress of Mathematicians (ICM). 659-682. · Zbl 1373.68246 |
| [89] | Ryan Williams. 2014. New algorithms and lower bounds for circuits with linear threshold gates. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC). 194-202. 10.1145/2591796.2591858 · Zbl 1315.68142 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
