{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T18:40:42Z","timestamp":1698864042211},"reference-count":22,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. ^|^ Syst."],"published-print":{"date-parts":[[2015]]},"DOI":"10.1587\/transinf.2014edp7127","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T07:25:07Z","timestamp":1420442707000},"page":"108-118","source":"Crossref","is-referenced-by-count":2,"title":["A Satisfiability Algorithm for Some Class of Dense Depth Two Threshold Circuits"],"prefix":"10.1587","volume":"E98.D","author":[{"given":"Kazuyuki","family":"AMANO","sequence":"first","affiliation":[{"name":"Department of Computer Science, Gunma University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atsushi","family":"SAITO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Gunma University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] A. Biere, A. Cimatti, E. Clarke, and Y. Zhu, \u201cSymbolic modelchecking without BDDs,\u201d in Tools and Algorithms for the Construction and Analysis of Systems, pp.193-207, 1999.","DOI":"10.1007\/3-540-49059-0_14"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] R.B. Boppana and M. Sipser, \u201cThe complexity of finite functions,\u201d in Handbook of theoretical computer science (vol.a), pp.757-804, MIT Press, Cambridge, MA, USA, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"3","unstructured":"[3] C. Calabro, \u201cThe exponential complexity of satisfiability problems,\u201d PhD thesis, University of California, San Diego, 2009."},{"key":"4","unstructured":"[4] C. Calabro, R. Impagliazzo, and R. Paturi, \u201cThe complexity of satisfiability of small depth circuits,\u201d Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, Sept. 2009, Revised Selected Papers, pp.75-85, Springer-Verlag, Berlin, Heidelberg, 2009."},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] A.K. Chandra, L. Stockmeyer, and U. Vishkin, \u201cConstant depth reducibility,\u201d SIAM J. on Comput, vol.13, no.2, pp.423-439, 1984.","DOI":"10.1137\/0213028"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] S.A. Cook, \u201cThe complexity of theorem-proving procedures,\u201d Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp.151-158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] E. Dantsin and A. Wolpert, \u201cMax-SAT for formulas with constant clause density can be solved faster than in <i>O<\/i>(2<i><sup>n<\/sup><\/i>) time,\u201d in Armin Biere and CarlaP. Gomes, editors, Theory and Applications of Satisfiability Testing-SAT 2006, Lecture Notes in Computer Science, vol.4121, pp.266-276, Springer Berlin Heidelberg, 2006.","DOI":"10.1007\/11814948_26"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, and G. Turan, \u201cThreshold circuits of bounded depth,\u201d Proceedings of the 28th Annual Symposium on Foundations of Computer Science, FOCS&apos;87, pp.99-110, IEEE Computer Society, Washington, DC, USA, 1987.","DOI":"10.1109\/SFCS.1987.59"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] R. Impagliazzo and R. Paturi, \u201cThe complexity of k-SAT,\u201d Journal of Computer and Systems Sciences, vol.62, no.2, pp.367-375, March 2001. Preliminary version in 14th Annual IEEE Conference on Computational Complexity, pp.237-240, 1999.","DOI":"10.1006\/jcss.2000.1727"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] R. Impagliazzo, R. Paturi, and F. Zane, \u201cWhich problems have strongly exponential complexity?,\u201d J. Computer and System Sciences, vol.63, pp.512-530, 1998. Preliminary version in 39th Annual IEEE Symposium on Foundations of Computer Science, pp.653-662, 1998.","DOI":"10.1006\/jcss.2001.1774"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] R. Impagliazzo, W. Matthews, and R. Paturi, \u201cA satisfiability algorithm for AC0,\u201d Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp.961-972, 2012.","DOI":"10.1137\/1.9781611973099.77"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] R. Impagliazzo, R. Paturi, and M.E. Saks, \u201cSize-depth tradeoffs for threshold circuits,\u201d SIAM J. Comput., vol.26, no.3, pp.693-707, 1997. Preliminary version published in STOC 1993.","DOI":"10.1137\/S0097539792282965"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] R. Impagliazzo, R. Paturi, and S. Schneider, \u201cA satisfiability algorithm for sparse depth two threshold circuits,\u201d FOCS&apos;13, pp.479-488, 2013.","DOI":"10.1109\/FOCS.2013.58"},{"key":"14","unstructured":"[14] L. Levin, \u201cUniversal sorting problems,\u201d Problems of Information Transmission, vol.9, pp.265-266, 1973."},{"key":"15","unstructured":"[15] I. Lynce and J. Marques-Silva, \u201cEfficient haplotype inference with Boolean satisfiability,\u201d National Conference on Artificial Intelligence, pp.104-109, July 2006."},{"key":"16","unstructured":"[16] R. Santhanam, \u201cFighting perebor: New and improved algorithms for formula and qbf satisfiability,\u201d Proc. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS10, pp.183-192, IEEE Computer Society, Washington, DC, USA, 2010."},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] R. Schuler, \u201cAn algorithm for the satisfiability problem of formulas in conjunctive normal form,\u201d Journal of Algorithms, vol.54, no.1, pp.40-44, 2005.","DOI":"10.1016\/j.jalgor.2004.04.012"},{"key":"18","unstructured":"[18] A. Smith, A.G. Veneris, M.F. Ali, and A. Viglas, \u201cFault diagnosis and logic debugging using Boolean satisfiability,\u201d IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol.24, no.10, pp.1606-1621, 2005."},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] R. Williams, \u201cA new algorithm for optimal 2-constraint satisfaction and its implications,\u201d Theoretical Computer Science, vol.348, pp.357-365, 2005.","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] R. Williams, \u201cImproving exhaustive search implies superpolynomial lower bounds,\u201d Proc. 42nd ACM symposium on Theory of computing, STOC&apos;10, pp.231-240, ACM, New York, NY, USA, 2010.","DOI":"10.1145\/1806689.1806723"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] R. Williams, \u201cNon-uniform ACC circuit lower bounds,\u201d Proc. Twenty-Sixth Annual IEEE Conference on Computational Complexity, pp.115-125, 2011.","DOI":"10.1109\/CCC.2011.36"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] R. Williams, \u201cNew algorithms and lower bounds for circuits with linear threshold gates,\u201d Proc. 46th ACM symposium on Theory of computing, STOC&apos;14, pp.194-202, 2014.","DOI":"10.1145\/2591796.2591858"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/1\/E98.D_2014EDP7127\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T23:15:20Z","timestamp":1650928520000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/1\/E98.D_2014EDP7127\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014edp7127","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}