Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
93 | Venkatesan Guruswami, Subhash Khot |
Hardness of Max 3SAT with No Mixed Clauses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pp. 154-162, 2005, IEEE Computer Society, 0-7695-2364-1. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
83 | Michael Krivelevich, Dan Vilenchik |
Solving random satisfiable 3CNF formulas in expected polynomial time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 454-463, 2006, ACM Press, 0-89871-605-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
76 | Rani Siromoney, Bireswar Das |
Plasmids to Solve #3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Aspects of Molecular Computing ![In: Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday, pp. 361-366, 2004, Springer, 3-540-20781-3. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
76 | Howard J. Karloff, Uri Zwick |
A 7/8-Approximation Algorithm for MAX 3SAT? ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pp. 406-415, 1997, IEEE Computer Society, 0-8186-8197-7. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
60 | Daniel J. Hulme, Robin Hirsch, Bernard F. Buxton, R. Beau Lotto |
A New Reduction from 3SAT to n-Partite Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCI ![In: Proceedings of the IEEE Symposium on Foundations of Computational Intelligence, FOCI 2007, part of the IEEE Symposium Series on Computational Intelligence 2007, Honolulu, Hawaii, USA, 1-5 April 2007, pp. 235-238, 2007, IEEE, 1-4244-0703-6. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
60 | Michael de Mare, Rebecca N. Wright |
Secure Set Membership Using 3Sat. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICICS ![In: Information and Communications Security, 8th International Conference, ICICS 2006, Raleigh, NC, USA, December 4-7, 2006, Proceedings, pp. 452-468, 2006, Springer, 3-540-49496-0. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
60 | Mitsuo Motoki |
Random Instance Generation for MAX 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings, pp. 502-508, 2001, Springer, 3-540-42494-6. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
50 | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001 |
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 35(4), pp. 449-463, 2002. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
50 | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001 |
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, pp. 51-62, 2001, Springer, 3-540-41695-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
46 | Dominique Attali, André Lieutier |
Optimal reconstruction might be hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SCG ![In: Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pp. 334-343, 2010, ACM, 978-1-4503-0016-2. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
3SAT, homological simplification, sampling conditions, topological persistence, NP-completeness, shape reconstruction |
46 | Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor |
The Power of Unentanglement. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 223-236, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement |
46 | Uriel Feige |
Relations between Average Case Complexity and Approximation Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 5, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
random 3sat, bipartite clique, bisection |
46 | Eric Bach 0001, Anne Condon, Elton Glaser, Celena Tanguay |
DNA Models and Algorithms for NP-complete Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pp. 290-300, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
3Sat, 3-Coloring, Independent Set problem, DNA algorithms, genetic algorithms, computational complexity, search problems, DNA computing, DNA computation, NP-complete problems, search algorithms, NP-hard problems |
33 | Dana Moshkovitz, Ran Raz |
Two Query PCP with Sub-Constant Error. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pp. 314-323, 2008, IEEE Computer Society, 978-0-7695-3436-7. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
33 | Tianyan Deng, Daoyun Xu |
Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICYCS ![In: Proceedings of the 9th International Conference for Young Computer Scientists, ICYCS 2008, Zhang Jia Jie, Hunan, China, November 18-21, 2008, pp. 60-64, 2008, IEEE Computer Society, 978-0-7695-3398-8. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
33 | Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb |
Private approximation of search problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 119-128, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
private approximation, solution-list algorithm, vertex cover, secure computation |
33 | Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis |
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 294-303, 2005, ACM, 1-58113-960-8. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
Lovász-Schrijver matrix cuts, inapproximability, integrality gaps |
33 | Venkatesan Guruswami |
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithmica ![In: Algorithmica 38(3), pp. 451-469, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
Set splitting, Hardness of approximations, PCP, Gadgets |
33 | Luca Trevisan |
Non-approximability results for optimization problems on bounded degree instances. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pp. 453-461, 2001, ACM, 1-58113-349-9. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
33 | David P. Williamson |
Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: Graph-Theoretic Concepts in Computer Science, 23rd International Workshop, WG '97, Berlin, Germany, June 18-20, 1997, Proceedings, pp. 1, 1997, Springer, 3-540-63757-5. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
27 | Darrell Whitley, Gabriela Ochoa, Noah Floyd, Francisco Chicano |
Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EvoStar ![In: Evolutionary Computation in Combinatorial Optimization - 24th European Conference, EvoCOP 2024, Held as Part of EvoStar 2024, Aberystwyth, UK, April 3-5, 2024, Proceedings, pp. 113-128, 2024, Springer, 978-3-031-57711-6. The full citation details ...](Pics/full.jpeg) |
2024 |
DBLP DOI BibTeX RDF |
|
27 | M. Hüsrev Cilasun, Ziqing Zeng, Ramprasath S 0001, Abhimanyu Kumar, Hao Lo, William Cho, Chris H. Kim, Ulya R. Karpuzcu, Sachin S. Sapatnekar |
3SAT on an All-to-All-Connected CMOS Ising Solver Chip. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2309.11017, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
27 | Sebastian Zielinski, Jonas Nüßlein, Jonas Stein 0001, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld |
Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study. ![Search on Bibsonomy](Pics/bibsonomy.png) |
GECCO Companion ![In: Companion Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO 2023, Companion Volume, Lisbon, Portugal, July 15-19, 2023, pp. 2263-2271, 2023, ACM. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
27 | Samuel Deleplanque |
Solving 3SAT and MIS Problems with Analog Quantum Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICCSA (Workshops 1) ![In: Computational Science and Its Applications - ICCSA 2023 Workshops - Athens, Greece, July 3-6, 2023, Proceedings, Part I, pp. 429-439, 2023, Springer, 978-3-031-37104-2. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
27 | Tong Qin, Osamu Watanabe |
An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEICE Trans. Inf. Syst. ![In: IEICE Trans. Inf. Syst. 105-D(3), pp. 481-490, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
27 | Shyan Akmal, R. Ryan Williams |
MAJORITY-3SAT (and Related Problems) in Polynomial Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2107.02748, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
27 | Shyan Akmal, Ryan Williams 0001 |
MAJORITY-3SAT (and Related Problems) in Polynomial Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pp. 1033-1043, 2021, IEEE, 978-1-6654-2055-6. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
27 | Chuzo Iwamoto, Tatsuaki Ibusuki |
Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEICE Trans. Inf. Syst. ![In: IEICE Trans. Inf. Syst. 103-D(3), pp. 500-505, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
27 | Tong Qin 0003, Osamu Watanabe 0001 |
An improvement of the algorithm of Hertli for the unique 3SAT problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 806, pp. 70-80, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
27 | Latif Salum |
Tractability of One-in-three 3SAT: P = NP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2012.06304, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
27 | Thomas Gabor, Sebastian Zielinski, Sebastian Feld, Christoph Roch, Christian Seidel, Florian Neukart, Isabella Galter, Wolfgang Mauerer, Claudia Linnhoff-Popien |
Assessing Solution Quality of 3SAT on a Quantum Annealing Platform. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1902.04703, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
27 | Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen |
The threshold for SDP-refutation of random regular NAE-3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 2305-2321, 2019, SIAM, 978-1-61197-548-2. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
27 | Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen |
The threshold for SDP-refutation of random regular NAE-3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1804.05230, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
27 | Matthew Delacorte |
Solving 3SAT By Reduction To Testing For Odd Hole. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1810.00875, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
27 | Tong Qin 0003, Osamu Watanabe 0001 |
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WALCOM ![In: WALCOM: Algorithms and Computation - 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings, pp. 93-105, 2018, Springer, 978-3-319-75171-9. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
27 | Tong Qin 0003, Osamu Watanabe 0001 |
An improvement of the algorithm of Hertli for the unique 3SAT problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR17, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
27 | Cristian Dumitrescu |
A randomized, efficient algorithm for 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1703.01905, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
27 | Byoungkwon An, Erik D. Demaine, Martin L. Demaine, Jason S. Ku |
Computing 3SAT on a Fold-and-Cut Machine. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCCG ![In: Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada, pp. 208-213, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
27 | Thomas Gabor, Sebastian Zielinski, Sebastian Feld, Christoph Roch, Christian Seidel, Florian Neukart, Isabella Galter, Wolfgang Mauerer, Claudia Linnhoff-Popien |
Assessing Solution Quality of 3SAT on a Quantum Annealing Platform. ![Search on Bibsonomy](Pics/bibsonomy.png) |
QTOP@NetSys ![In: Quantum Technology and Optimization Problems - First International Workshop, QTOP@NetSys 2019, Munich, Germany, March 18, 2019, Proceedings, pp. 23-35, 2017, Springer, 978-3-030-14081-6. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
27 | Irit Dinur |
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
27 | Lidong Wu |
On strongly planar 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 32(1), pp. 293-298, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
27 | Ali Dehghan 0001 |
On strongly planar not-all-equal 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 32(3), pp. 721-724, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
27 | Koh-ichi Nagao |
Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2015, pp. 985, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
27 | Iddo Tzameret |
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR13, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP BibTeX RDF |
|
27 | Iddo Tzameret |
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1305.0948, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP BibTeX RDF |
|
27 | Artur García-Sáez, José Ignacio Latorre |
An exact tensor network for the 3SAT problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Quantum Inf. Comput. ![In: Quantum Inf. Comput. 12(3-4), pp. 283-292, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|
27 | Chuzo Iwamoto, Kento Sasaki, Kenichi Morita |
A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithms ![In: Algorithms 5(2), pp. 261-272, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|
27 | Artur García-Sáez, José Ignacio Latorre |
An exact tensor network for the 3SAT problem ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1105.3201, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP BibTeX RDF |
|
27 | Vicky Choi |
Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1004.2226, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
27 | Vicky Choi |
Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1010.1221, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
27 | Peiyush Jain |
On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1003.3704, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
27 | Luigi Salemi |
Method of resolution of 3SAT in polynomial time ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/0909.3868, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP BibTeX RDF |
|
27 | Wenceslas Fernandez de la Vega, Marek Karpinski |
1.0957-Approximation Algorithm for Random MAX-3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
RAIRO Oper. Res. ![In: RAIRO Oper. Res. 41(1), pp. 95-103, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
27 | B. Subramaniam, Rani Siromoney |
Contextial Insertion for #3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Bull. EATCS ![In: Bull. EATCS 88, pp. 174-181, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP BibTeX RDF |
|
27 | Honglei Zeng, Sheila A. McIlraith |
Experimental Results on the Satisfiable Core in Random 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
AI&M ![In: International Symposium on Artificial Intelligence and Mathematics, AI&Math 2006, Fort Lauderdale, Florida, USA, January 4-6, 2006, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP BibTeX RDF |
|
27 | Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström |
Counting models for 2SAT and 3SAT formulae. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 332(1-3), pp. 265-291, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Piotr Berman, Marek Karpinski, Alexander D. Scott |
Computational Complexity of Some Restricted Instances of 3SAT ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR04, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
27 | Piotr Berman, Marek Karpinski, Alex D. Scott |
Approximation Hardness of Short Symmetric Instances of MAX-3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR03, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP BibTeX RDF |
|
27 | Wenceslas Fernandez de la Vega, Marek Karpinski |
9/8-Approximation Algorithm for Random MAX-3SAT ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR02, 2002. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP BibTeX RDF |
|
27 | Tuomas Sandholm |
A Second Order Parameter for 3SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
AAAI/IAAI, Vol. 1 ![In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI 96, Portland, Oregon, USA, August 4-8, 1996, Volume 1., pp. 259-265, 1996, AAAI Press / The MIT Press, 0-262-51091-X. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP BibTeX RDF |
|
17 | Dániel Marx |
Tractable hypergraph properties for constraint satisfaction and conjunctive queries. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 735-744, 2010, ACM, 978-1-4503-0050-6. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
submodular width, constraint satisfaction, conjunctive queries, fixed-parameter tractability |
17 | Lusheng Wang 0001, Binhai Zhu |
On the Tractability of Maximal Strip Recovery. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TAMC ![In: Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings, pp. 400-409, 2009, Springer, 978-3-642-02016-2. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
17 | Tianyan Deng, Daoyun Xu |
NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k). ![Search on Bibsonomy](Pics/bibsonomy.png) |
FAW ![In: Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings, pp. 79-88, 2008, Springer, 978-3-540-69310-9. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
PCP theorem, linear CNF formula, LSAT, minimal unsatisfiable(MU) formula, NP-completeness, reduction |
17 | Peter Gregory, Maria Fox 0001, Derek Long |
A New Empirical Study of Weak Backdoors. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CP ![In: Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008. Proceedings, pp. 618-623, 2008, Springer, 978-3-540-85957-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
17 | David Nistér, Fredrik Kahl, Henrik Stewénius |
Structure from Motion with Missing Data is NP-Hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICCV ![In: IEEE 11th International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14-20, 2007, pp. 1-7, 2007, IEEE Computer Society, 978-1-4244-1630-1. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
17 | Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink |
Application of Mismatch Detection Methods in DNA Computing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Nat. Comput. ![In: Nat. Comput. 5(2), pp. 151-163, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
mismatch detection, mutation detection, DNA computing, DNA hybridization |
17 | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour |
Combination can be hard: approximability of the unique coverage problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 162-171, 2006, ACM Press, 0-89871-605-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
17 | Alexandr Andoni, Piotr Indyk, Mihai Patrascu |
On the Optimality of the Dimensionality Reduction Method. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 449-458, 2006, IEEE Computer Society, 0-7695-2720-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
17 | Johan Håstad |
On Nontrivial Approximation of CSPs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp. 1, 2006, Springer, 3-540-38044-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
17 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
On Pseudorandom Generators with Linear Stretch in NC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp. 260-271, 2006, Springer, 3-540-38044-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
17 | Uriel Feige, Elchanan Mossel, Dan Vilenchik |
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp. 339-350, 2006, Springer, 3-540-38044-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
17 | Subhash Khot |
Guest column: inapproximability results via Long Code based PCPs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIGACT News ![In: SIGACT News 36(2), pp. 25-42, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
17 | Magnus Wahlström |
An Algorithm for the SAT Problem for Formulae of Linear Length. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESA ![In: Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, pp. 107-118, 2005, Springer, 3-540-29118-0. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
17 | Maurizio Patrignani |
Complexity Results for Three-Dimensional Orthogonal Graph Drawing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
GD ![In: Graph Drawing, 13th International Symposium, GD 2005, Limerick, Ireland, September 12-14, 2005, Revised Papers, pp. 368-379, 2005, Springer, 3-540-31425-3. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
17 | Iannis Tourlakis |
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, pp. 233-244, 2005, Springer, 3-540-28239-4. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
17 | Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink |
Application of Mismatch Detection Methods in DNA Computing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
DNA ![In: DNA Computing, 10th International Workshop on DNA Computing, DNA 10, Milan, Italy, June 7-10, 2004, Revised Selected Papers, pp. 159-168, 2004, Springer, 3-540-26174-5. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
17 | Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond |
An FPT Algorithm for Set Splitting. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: Graph-Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers, pp. 180-191, 2003, Springer, 3-540-20452-0. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
17 | Ryan Williams 0001 |
On Computing k-CNF Formula Properties. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SAT ![In: Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5-8, 2003 Selected Revised Papers, pp. 330-340, 2003, Springer, 3-540-20851-8. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
17 | Emese Balogh, Attila Kuba, Alberto Del Lungo, Maurice Nivat |
Reconstruction of Binary Matrices from Absorbed Projections. ![Search on Bibsonomy](Pics/bibsonomy.png) |
DGCI ![In: Discrete Geometry for Computer Imagery, 10th International Conference, DGCI 2002, Bordeaux, France, April 3-5, 2002, Proceedings, pp. 392-403, 2002, Springer, 3-540-43380-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
absorption, reconstruction, discrete tomography |
17 | Peter J. Stuckey, Lei Zheng |
Improving GSAT Using 2SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CP ![In: Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, pp. 691-695, 2002, Springer, 3-540-44120-4. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
17 | Uriel Feige |
Relations between average case complexity and approximation complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pp. 534-543, 2002, ACM, 1-58113-495-9. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
17 | Kazuo Iwama, Suguru Tamaki |
Exploiting Partial Knowledge of Satisfying Assignments. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WAE ![In: Algorithm Engineering, 5th International Workshop, WAE 2001 Aarhus, Denmark, August 28-31, 2001, Proceedings, pp. 118-128, 2001, Springer, 3-540-42500-4. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
17 | Makoto Yokoo, Katsutoshi Hirayama |
The Effect of Nogood Learning in Distributed Constraint Satisfaction. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICDCS ![In: Proceedings of the 20th International Conference on Distributed Computing Systems, Taipei, Taiwan, April 10-13, 2000, pp. 169-177, 2000, IEEE Computer Society, 0-7695-0601-1. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
17 | Venkatesan Guruswami |
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX ![In: Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pp. 155-166, 2000, Springer, 3-540-67996-0. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
17 | Limor Drori, David Peleg |
Faster Exact Solutions for Some NP-Hard Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESA ![In: Algorithms - ESA '99, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings, pp. 450-461, 1999, Springer, 3-540-66251-0. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
17 | Mario Szegedy |
Many-Valued Logics and Holographic Proofs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings, pp. 676-686, 1999, Springer, 3-540-66224-3. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
17 | Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns |
Approximation Schemes Using L-Reductions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FSTTCS ![In: Foundations of Software Technology and Theoretical Computer Science, 14th Conference, Madras, India, December 15-17, 1994, Proceedings, pp. 342-353, 1994, Springer, 3-540-58715-2. The full citation details ...](Pics/full.jpeg) |
1994 |
DBLP DOI BibTeX RDF |
|
17 | Peter Damaschke |
Induced Subgraph Isomorphism for Cographs in NP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings, pp. 72-78, 1990, Springer, 3-540-53832-1. The full citation details ...](Pics/full.jpeg) |
1990 |
DBLP DOI BibTeX RDF |
|