Proving SAT does not have Small Circuits with an Application to the Two Queries Problem. Fortnow, L., Pavan, A., & Sengupta, S. Journal of Computer and System Sciences, 74(3):358-363, May, 2008. Special issue for selected papers from the 18th IEEE Conference on Computational Complexity
![Proving SAT does not have Small Circuits with an Application to the Two Queries Problem [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper ![Proving SAT does not have Small Circuits with an Application to the Two Queries Problem [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper doi bibtex 2 downloads
Paper Paper doi bibtex 2 downloads @article{satcirc-J,
show = 1,
title = "Proving {SAT} does not have Small Circuits with
an Application to the Two Queries Problem",
author = "L. Fortnow and A. Pavan and S. Sengupta",
journal = jcss,
year = 2008,
month = may,
volume = 74,
number = 3,
pages = "358-363",
url = "https://dx.doi.org/10.1016/j.jcss.2007.06.017",
doi = "10.1016/j.jcss.2007.06.017",
note = "Special issue for selected papers from the 18th IEEE
Conference on Computational Complexity",
url_Paper = "https://lance.fortnow.com/papers/files/2q.pdf"}Downloads: 2
{"_id":"vRh8A5QvRm3s72jck","bibbaseid":"fortnow-pavan-sengupta-provingsatdoesnothavesmallcircuitswithanapplicationtothetwoqueriesproblem-2008","downloads":2,"creationDate":"2016-02-09T20:07:42.569Z","title":"Proving SAT does not have Small Circuits with an Application to the Two Queries Problem","author_short":["Fortnow, L.","Pavan, A.","Sengupta, S."],"year":2008,"bibtype":"article","biburl":"https://github.com/fortnow/pubs2/raw/master/pubs.bib","bibdata":{"bibtype":"article","type":"article","show":"1","title":"Proving SAT does not have Small Circuits with an Application to the Two Queries Problem","author":[{"firstnames":["L."],"propositions":[],"lastnames":["Fortnow"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Pavan"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Sengupta"],"suffixes":[]}],"journal":"Journal of Computer and System Sciences","year":"2008","month":"May","volume":"74","number":"3","pages":"358-363","url":"https://dx.doi.org/10.1016/j.jcss.2007.06.017","doi":"10.1016/j.jcss.2007.06.017","note":"Special issue for selected papers from the 18th IEEE Conference on Computational Complexity","url_paper":"https://lance.fortnow.com/papers/files/2q.pdf","bibtex":"@article{satcirc-J,\nshow = 1,\ntitle = \"Proving {SAT} does not have Small Circuits with\nan Application to the Two Queries Problem\",\nauthor = \"L. Fortnow and A. Pavan and S. Sengupta\",\njournal = jcss,\nyear = 2008,\nmonth = may,\nvolume = 74,\nnumber = 3,\npages = \"358-363\",\nurl = \"https://dx.doi.org/10.1016/j.jcss.2007.06.017\",\ndoi = \"10.1016/j.jcss.2007.06.017\",\nnote = \"Special issue for selected papers from the 18th IEEE\nConference on Computational Complexity\",\nurl_Paper = \"https://lance.fortnow.com/papers/files/2q.pdf\"}\n\n","author_short":["Fortnow, L.","Pavan, A.","Sengupta, S."],"key":"satcirc-J","id":"satcirc-J","bibbaseid":"fortnow-pavan-sengupta-provingsatdoesnothavesmallcircuitswithanapplicationtothetwoqueriesproblem-2008","role":"author","urls":{"Paper":"https://dx.doi.org/10.1016/j.jcss.2007.06.017"," paper":"https://lance.fortnow.com/papers/files/2q.pdf"},"metadata":{"authorlinks":{"fortnow, l":"https://lance.fortnow.com/papers/"}},"downloads":2},"search_terms":["proving","sat","small","circuits","application","two","queries","problem","fortnow","pavan","sengupta"],"keywords":[],"authorIDs":["2MfjZGeXKGftSpfyx","2aH8tvwCiWycaA5Bh","4ALebC8HYfmho9EGx","4By8is8Afn9aa4LMg","4DhPp9FtrA4Tn9M4e","4i4isCBncFZXjsrQf","56ba470d16a1deb95500038d","5de813119b61e8de01000240","5de9ba5d5b51bcde0100012b","5dedd32b0e26d5de01000042","5df00fc4e128adde010000e4","5df22b2a1e4fe9df0100014e","5e0511d1e11806de010000f5","5e0943b4934cacdf010000a9","5e0ce30f6762d1de01000152","5e0fdebc063b5cde01000018","5e10f37e45c12cde010000fe","5e1295b6551229df0100009d","5e14290912768ef30100001a","5e1f22b807379ade01000002","5e23e476075528de0100002f","5e24d27e981ceddf010000ab","5e266ccb581147f20100007d","5e26b72c8535cedf01000002","5e2b87136f2b8ade0100015e","5e43a6f4a3f5a4de01000080","5e45b6490920e8de01000033","5e51b04832046bdf01000033","5e64bd31a8ac14df0100009d","5e64e2050b8008df010000a6","5e64f0755fc0b7de01000048","5e6684dd152d6bde010001e0","6WCHcyz7iqCZZqX69","7MQSPruXej8XLNeWY","8BCpnyQf6a68XSrbx","8wkgbFn6MvFeirpKY","9PxRaoKN5AEFE7sg3","Azt5NBTqEdNj9ZoNP","CGCmuaWv9BhamfTZp","FG5QJnC4PB9Hi9Nvu","FmPkiQd4kKY2ieEQc","JFaywov8yBspxFgcb","JK4d9mKyjYR8fQfHR","LJScFAMn6FHEC7ALg","LcC8GAnsSBcGhvNEA","MHHwKmwWkM3fuSYCR","Mfm9yXSz5BFRR7m5n","NK7A9dEhhrmbsQxNi","PwkRNRLFSzdAuysoW","PxbkvqKvgQrCvQDR4","SDjaWmBpp4SBwhYdX","TooEnGNeHDQ7z9skK","Wgkzpxqaf8as8ifzW","Y5G36wD7JqPsJrTBE","cbQ5atCaqRLRC9rkv","eTLWnE6xRsmguaW3B","eryhipBQvrNtQ7aex","kvPL5BdW9YJhM5Aq3","moAn8atNGjxREfcE4","uLHm73sBwoQ55wHGa","vCD2s6ecFfi7v7pJx","vxowKAqiu4HJeGmyX","wZLWgdmFCCyme7jmC","wd7X54rvHCkDLSyJc","y2CMMPzcPBiJQPMsN","zmMnvrcF6kQ4GBmMF"],"dataSources":["Qo8NuaKyuaTqZRa6n","oWB3XQwMpuvaY9GG2","Pku8vFzFhtx9p7pE6","uKt7RQWEWWvqzsXYy"]}