{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:04Z","timestamp":1740109324552,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2017\/000909","MTR\/2017\/000958"],"award-info":[{"award-number":["MTR\/2017\/000909","MTR\/2017\/000958"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00453-021-00915-7","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T20:02:26Z","timestamp":1641585746000},"page":"1132-1162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates"],"prefix":"10.1007","volume":"84","author":[{"given":"Swapnam","family":"Bajpai","sequence":"first","affiliation":[]},{"given":"Vaibhav","family":"Krishan","sequence":"additional","affiliation":[]},{"given":"Deepanshu","family":"Kush","sequence":"additional","affiliation":[]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"unstructured":"Abboud, A., Bringmann, K.: Tighter connections between formula-sat and shaving logs. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic, pp. 8:1\u20138:18 (2018)","key":"915_CR1"},{"doi-asserted-by":"crossref","unstructured":"Abboud, A., Hansen, T.D., Williams, V.V., Williams, R.: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 375\u2013388 (2016)","key":"915_CR2","DOI":"10.1145\/2897518.2897653"},{"unstructured":"Abboud, A., Rubinstein, A.: Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11\u201314, 2018, Cambridge, MA, USA, pp. 35:1\u201335:14 (2018)","key":"915_CR3"},{"issue":"4","key":"915_CR4","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P Beame","year":"1986","unstructured":"Beame, P., Cook, S.A., Hoover, H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15(4), 994\u20131003 (1986)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Chow, C-K.: On the characterization of threshold functions. In: Switching Circuit Theory and Logical Design, 1961. SWCT 1961. Proceedings of the Second Annual Symposium on Switching Circuit Theory and Logical Design, pp. 34\u201338. IEEE (1961)","key":"915_CR5","DOI":"10.1109\/FOCS.1961.24"},{"doi-asserted-by":"crossref","unstructured":"Chen, R., Santhanam, R.: Improved algorithms for sparse max-sat and max-k-csp. In: International Conference on Theory and Applications of Satisfiability Testing, pp. 33\u201345. Springer, Berlin (2015)","key":"915_CR6","DOI":"10.1007\/978-3-319-24318-4_4"},{"issue":"1","key":"915_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2018.v014a009","volume":"14","author":"R Chen","year":"2018","unstructured":"Chen, R., Santhanam, R., Srinivasan, S.: Average-case lower bounds and satisfiability algorithms for small threshold circuits. Theory Comput. 14(1), 1\u201355 (2018)","journal-title":"Theory Comput."},{"unstructured":"Chen, L., Williams, R.R.: Stronger connections between circuit analysis and circuit lower bounds, via pcps of proximity. In: 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)","key":"915_CR8"},{"key":"915_CR9","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M Goldmann","year":"1992","unstructured":"Goldmann, M., H\u00e5stad, J., Razborov, A.A.: Majority gates VS. general weighted threshold gates. Comput. Complex. 2, 277\u2013300 (1992)","journal-title":"Comput. Complex."},{"issue":"4","key":"915_CR10","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4), 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Hofmeister, T.: A note on the simulation of exponential threshold weights. In: International Computing and Combinatorics Conference, pp. 136\u2013141. Springer, Berlin (1996)","key":"915_CR11","DOI":"10.1007\/3-540-61332-3_146"},{"doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Podolskii, V.V.: Exact threshold circuits. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9\u201312, 2010, pp. 270\u2013279 (2010)","key":"915_CR12","DOI":"10.1109\/CCC.2010.33"},{"key":"915_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ic.2014.09.008","volume":"240","author":"KA Hansen","year":"2015","unstructured":"Hansen, K.A., Podolskii, V.V.: Polynomial threshold functions and Boolean threshold circuits. Inf. Comput. 240, 56\u201373 (2015)","journal-title":"Inf. Comput."},{"key":"915_CR14","first-page":"24","volume":"21","author":"R Impagliazzo","year":"2014","unstructured":"Impagliazzo, R., Lovett, S., Paturi, R., Schneider, S.: 0\u20131 integer linear programming with a linear number of constraints. Electron. Colloquium Comput. Complex. (ECCC) 21, 24 (2014)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"issue":"3","key":"915_CR15","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/S0097539792282965","volume":"26","author":"R Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Paturi, R., Saks, M.E.: Size-depth tradeoffs for threshold circuits. SIAM J. Comput. 26(3), 693\u2013707 (1997)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013, pp. 479\u2013488. IEEE (2013)","key":"915_CR16","DOI":"10.1109\/FOCS.2013.58"},{"doi-asserted-by":"crossref","unstructured":"Kabanets, V., Kane, D.M., Lu, Z.: A polynomial restriction lemma with applications. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 615\u2013628. ACM (2017)","key":"915_CR17","DOI":"10.1145\/3055399.3055470"},{"unstructured":"Kabanets, V., Lu, Z.: Satisfiability and derandomization for small polynomial threshold circuits. In: Eric, B., Klaus, J., Jos\u00e9 D.P.R., David, S. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018, August 20\u201322, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pp. 46:1\u201346:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)","key":"915_CR18"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Lovett, S., Moran, S.: Near-optimal linear decision trees for k-sum and related problems. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25\u201329, 2018, pp. 554\u2013563 (2018)","key":"915_CR19","DOI":"10.1145\/3188745.3188770"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Lovett, S., Moran, S., Zhang, J.: Active classification with comparison queries. In: Chris, U. (eds.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017, pp. 355\u2013366. IEEE Computer Society, New York (2017)","key":"915_CR20","DOI":"10.1109\/FOCS.2017.40"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Williams, R.: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 633\u2013643 (2016)","key":"915_CR21","DOI":"10.1145\/2897518.2897636"},{"key":"915_CR22","volume-title":"Threshold Logic and Its Applications","author":"S Muroga","year":"1971","unstructured":"Muroga, S.: Threshold Logic and Its Applications. Wiley, Hoboken (1971)"},{"issue":"2","key":"915_CR23","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231\u2013262 (2004)","journal-title":"J. ACM"},{"key":"915_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"915_CR25","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/090756466","volume":"40","author":"R O\u2019Donnell","year":"2011","unstructured":"O\u2019Donnell, R., Servedio, R.A.: The chow parameters problem. SIAM J. Comput. 40(1), 165\u2013199 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"915_CR26","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-sat. J. ACM (JACM) 52(3), 337\u2013364 (2005)","journal-title":"J. ACM (JACM)"},{"key":"915_CR27","first-page":"11","volume":"1999","author":"R Paturi","year":"1999","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chic. J. Theor. Comput. Sci. 1999, 11 (1999)","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"1","key":"915_CR28","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"AA Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: new and improved algorithms for formula and QBF satisfiability. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23\u201326, 2010, pp. 183\u2013192 (2010)","key":"915_CR29","DOI":"10.1109\/FOCS.2010.25"},{"unstructured":"Srinivasan, S.: On improved degree lower bounds for polynomial approximation. In: Anil, S., Nisheeth, K.V. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12\u201314, 2013, Guwahati, India, volume\u00a024 of LIPIcs, pp. 201\u2013212. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013)","key":"915_CR30"},{"unstructured":"Sakai, T., Seto, K., Tamaki, S., Teruyama, J.: Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), vol.\u00a058, pp. 82:1\u201382:16 (2016)","key":"915_CR31"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12\u201316, 2004. Proceedings, pp. 1227\u20131237 (2004)","key":"915_CR32","DOI":"10.1007\/978-3-540-27836-8_101"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 231\u2013240. ACM, London (2010)","key":"915_CR33","DOI":"10.1145\/1806689.1806723"},{"issue":"3","key":"915_CR34","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/2034575.2034591","volume":"42","author":"R Williams","year":"2011","unstructured":"Williams, R.: Guest column: a casual tour around a circuit complexity bound. SIGACT News 42(3), 54\u201376 (2011)","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 664\u2013673 (2014)","key":"915_CR35","DOI":"10.1145\/2591796.2591811"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 194\u2013202. ACM, New York (2014)","key":"915_CR36","DOI":"10.1145\/2591796.2591858"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1), 2:1\u20132:32 (2014)","key":"915_CR37","DOI":"10.1145\/2559903"},{"unstructured":"Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015., pp. 17\u201329 (2015)","key":"915_CR38"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00915-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00915-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00915-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:08:40Z","timestamp":1647443320000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00915-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,7]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["915"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00915-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,7]]},"assertion":[{"value":"30 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}