The FacetedDBLP logo    Search for: in:

Disable automatic phrases ?     Syntactic query expansion: ?

Searching for 3Sat with no syntactic query expansion in all metadata.

Publication years (Num. hits)
1990-2002 (20) 2003-2006 (25) 2007-2010 (15) 2011-2018 (16) 2019-2024 (12)
Publication types (Num. hits)
article(34) inproceedings(54)
Venues (Conferences, Journals, ...)
GrowBag graphs for keyword ? (Num. hits/coverage)

Group by:
The graphs summarize 29 occurrences of 27 keywords

Results
Found 88 publication records. Showing 88 according to the selection in the facets
Hits ? Authors Title Venue Year Link Author keywords
93Venkatesan Guruswami, Subhash Khot Hardness of Max 3SAT with No Mixed Clauses. Search on Bibsonomy CCC The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
83Michael Krivelevich, Dan Vilenchik Solving random satisfiable 3CNF formulas in expected polynomial time. Search on Bibsonomy SODA The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
76Rani Siromoney, Bireswar Das Plasmids to Solve #3SAT. Search on Bibsonomy Aspects of Molecular Computing The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
76Howard J. Karloff, Uri Zwick A 7/8-Approximation Algorithm for MAX 3SAT? Search on Bibsonomy FOCS The full citation details ... 1997 DBLP  DOI  BibTeX  RDF
60Daniel J. Hulme, Robin Hirsch, Bernard F. Buxton, R. Beau Lotto A New Reduction from 3SAT to n-Partite Graphs. Search on Bibsonomy FOCI The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
60Michael de Mare, Rebecca N. Wright Secure Set Membership Using 3Sat. Search on Bibsonomy ICICS The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
60Mitsuo Motoki Random Instance Generation for MAX 3SAT. Search on Bibsonomy COCOON The full citation details ... 2001 DBLP  DOI  BibTeX  RDF
50Shin 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 Theory Comput. Syst. The full citation details ... 2002 DBLP  DOI  BibTeX  RDF
50Shin 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 STACS The full citation details ... 2001 DBLP  DOI  BibTeX  RDF
46Dominique Attali, André Lieutier Optimal reconstruction might be hard. Search on Bibsonomy SCG The full citation details ... 2010 DBLP  DOI  BibTeX  RDF 3SAT, homological simplification, sampling conditions, topological persistence, NP-completeness, shape reconstruction
46Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor The Power of Unentanglement. Search on Bibsonomy CCC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
46Uriel Feige Relations between Average Case Complexity and Approximation Complexity. Search on Bibsonomy CCC The full citation details ... 2002 DBLP  DOI  BibTeX  RDF random 3sat, bipartite clique, bisection
46Eric Bach 0001, Anne Condon, Elton Glaser, Celena Tanguay DNA Models and Algorithms for NP-complete Problems. Search on Bibsonomy CCC The full citation details ... 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
33Dana Moshkovitz, Ran Raz Two Query PCP with Sub-Constant Error. Search on Bibsonomy FOCS The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
33Tianyan Deng, Daoyun Xu Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems. Search on Bibsonomy ICYCS The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
33Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb Private approximation of search problems. Search on Bibsonomy STOC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF private approximation, solution-list algorithm, vertex cover, secure computation
33Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Search on Bibsonomy STOC The full citation details ... 2005 DBLP  DOI  BibTeX  RDF Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
33Venkatesan Guruswami Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Search on Bibsonomy Algorithmica The full citation details ... 2004 DBLP  DOI  BibTeX  RDF Set splitting, Hardness of approximations, PCP, Gadgets
33Luca Trevisan Non-approximability results for optimization problems on bounded degree instances. Search on Bibsonomy STOC The full citation details ... 2001 DBLP  DOI  BibTeX  RDF
33David P. Williamson Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). Search on Bibsonomy WG The full citation details ... 1997 DBLP  DOI  BibTeX  RDF
27Darrell Whitley, Gabriela Ochoa, Noah Floyd, Francisco Chicano Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination. Search on Bibsonomy EvoStar The full citation details ... 2024 DBLP  DOI  BibTeX  RDF
27M. 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 CoRR The full citation details ... 2023 DBLP  DOI  BibTeX  RDF
27Sebastian 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 GECCO Companion The full citation details ... 2023 DBLP  DOI  BibTeX  RDF
27Samuel Deleplanque Solving 3SAT and MIS Problems with Analog Quantum Machines. Search on Bibsonomy ICCSA (Workshops 1) The full citation details ... 2023 DBLP  DOI  BibTeX  RDF
27Tong Qin, Osamu Watanabe An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem. Search on Bibsonomy IEICE Trans. Inf. Syst. The full citation details ... 2022 DBLP  DOI  BibTeX  RDF
27Shyan Akmal, R. Ryan Williams MAJORITY-3SAT (and Related Problems) in Polynomial Time. Search on Bibsonomy CoRR The full citation details ... 2021 DBLP  BibTeX  RDF
27Shyan Akmal, Ryan Williams 0001 MAJORITY-3SAT (and Related Problems) in Polynomial Time. Search on Bibsonomy FOCS The full citation details ... 2021 DBLP  DOI  BibTeX  RDF
27Chuzo Iwamoto, Tatsuaki Ibusuki Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles. Search on Bibsonomy IEICE Trans. Inf. Syst. The full citation details ... 2020 DBLP  BibTeX  RDF
27Tong Qin 0003, Osamu Watanabe 0001 An improvement of the algorithm of Hertli for the unique 3SAT problem. Search on Bibsonomy Theor. Comput. Sci. The full citation details ... 2020 DBLP  DOI  BibTeX  RDF
27Latif Salum Tractability of One-in-three 3SAT: P = NP. Search on Bibsonomy CoRR The full citation details ... 2020 DBLP  BibTeX  RDF
27Thomas 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 CoRR The full citation details ... 2019 DBLP  BibTeX  RDF
27Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen The threshold for SDP-refutation of random regular NAE-3SAT. Search on Bibsonomy SODA The full citation details ... 2019 DBLP  DOI  BibTeX  RDF
27Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen The threshold for SDP-refutation of random regular NAE-3SAT. Search on Bibsonomy CoRR The full citation details ... 2018 DBLP  BibTeX  RDF
27Matthew Delacorte Solving 3SAT By Reduction To Testing For Odd Hole. Search on Bibsonomy CoRR The full citation details ... 2018 DBLP  BibTeX  RDF
27Tong Qin 0003, Osamu Watanabe 0001 An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. Search on Bibsonomy WALCOM The full citation details ... 2018 DBLP  DOI  BibTeX  RDF
27Tong Qin 0003, Osamu Watanabe 0001 An improvement of the algorithm of Hertli for the unique 3SAT problem. Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2017 DBLP  BibTeX  RDF
27Cristian Dumitrescu A randomized, efficient algorithm for 3SAT. Search on Bibsonomy CoRR The full citation details ... 2017 DBLP  BibTeX  RDF
27Byoungkwon An, Erik D. Demaine, Martin L. Demaine, Jason S. Ku Computing 3SAT on a Fold-and-Cut Machine. Search on Bibsonomy CCCG The full citation details ... 2017 DBLP  BibTeX  RDF
27Thomas 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 QTOP@NetSys The full citation details ... 2017 DBLP  DOI  BibTeX  RDF
27Irit Dinur Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2016 DBLP  BibTeX  RDF
27Lidong Wu On strongly planar 3SAT. Search on Bibsonomy J. Comb. Optim. The full citation details ... 2016 DBLP  DOI  BibTeX  RDF
27Ali Dehghan 0001 On strongly planar not-all-equal 3SAT. Search on Bibsonomy J. Comb. Optim. The full citation details ... 2016 DBLP  DOI  BibTeX  RDF
27Koh-ichi Nagao Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system. Search on Bibsonomy IACR Cryptol. ePrint Arch. The full citation details ... 2015 DBLP  BibTeX  RDF
27Iddo Tzameret On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation. Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2013 DBLP  BibTeX  RDF
27Iddo Tzameret On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation Search on Bibsonomy CoRR The full citation details ... 2013 DBLP  BibTeX  RDF
27Artur García-Sáez, José Ignacio Latorre An exact tensor network for the 3SAT problem. Search on Bibsonomy Quantum Inf. Comput. The full citation details ... 2012 DBLP  DOI  BibTeX  RDF
27Chuzo Iwamoto, Kento Sasaki, Kenichi Morita A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem. Search on Bibsonomy Algorithms The full citation details ... 2012 DBLP  DOI  BibTeX  RDF
27Artur García-Sáez, José Ignacio Latorre An exact tensor network for the 3SAT problem Search on Bibsonomy CoRR The full citation details ... 2011 DBLP  BibTeX  RDF
27Vicky Choi Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems Search on Bibsonomy CoRR The full citation details ... 2010 DBLP  BibTeX  RDF
27Vicky Choi Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems Search on Bibsonomy CoRR The full citation details ... 2010 DBLP  BibTeX  RDF
27Peiyush Jain On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem Search on Bibsonomy CoRR The full citation details ... 2010 DBLP  BibTeX  RDF
27Luigi Salemi Method of resolution of 3SAT in polynomial time Search on Bibsonomy CoRR The full citation details ... 2009 DBLP  BibTeX  RDF
27Wenceslas Fernandez de la Vega, Marek Karpinski 1.0957-Approximation Algorithm for Random MAX-3SAT. Search on Bibsonomy RAIRO Oper. Res. The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
27B. Subramaniam, Rani Siromoney Contextial Insertion for #3SAT. Search on Bibsonomy Bull. EATCS The full citation details ... 2006 DBLP  BibTeX  RDF
27Honglei Zeng, Sheila A. McIlraith Experimental Results on the Satisfiable Core in Random 3SAT. Search on Bibsonomy AI&M The full citation details ... 2006 DBLP  BibTeX  RDF
27Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström Counting models for 2SAT and 3SAT formulae. Search on Bibsonomy Theor. Comput. Sci. The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
27Piotr Berman, Marek Karpinski, Alexander D. Scott Computational Complexity of Some Restricted Instances of 3SAT Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2004 DBLP  BibTeX  RDF
27Piotr Berman, Marek Karpinski, Alex D. Scott Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2003 DBLP  BibTeX  RDF
27Wenceslas Fernandez de la Vega, Marek Karpinski 9/8-Approximation Algorithm for Random MAX-3SAT Search on Bibsonomy Electron. Colloquium Comput. Complex. The full citation details ... 2002 DBLP  BibTeX  RDF
27Tuomas Sandholm A Second Order Parameter for 3SAT. Search on Bibsonomy AAAI/IAAI, Vol. 1 The full citation details ... 1996 DBLP  BibTeX  RDF
17Dániel Marx Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Search on Bibsonomy STOC The full citation details ... 2010 DBLP  DOI  BibTeX  RDF submodular width, constraint satisfaction, conjunctive queries, fixed-parameter tractability
17Lusheng Wang 0001, Binhai Zhu On the Tractability of Maximal Strip Recovery. Search on Bibsonomy TAMC The full citation details ... 2009 DBLP  DOI  BibTeX  RDF
17Tianyan Deng, Daoyun Xu NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k). Search on Bibsonomy FAW The full citation details ... 2008 DBLP  DOI  BibTeX  RDF PCP theorem, linear CNF formula, LSAT, minimal unsatisfiable(MU) formula, NP-completeness, reduction
17Peter Gregory, Maria Fox 0001, Derek Long A New Empirical Study of Weak Backdoors. Search on Bibsonomy CP The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
17David Nistér, Fredrik Kahl, Henrik Stewénius Structure from Motion with Missing Data is NP-Hard. Search on Bibsonomy ICCV The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
17Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink Application of Mismatch Detection Methods in DNA Computing. Search on Bibsonomy Nat. Comput. The full citation details ... 2006 DBLP  DOI  BibTeX  RDF mismatch detection, mutation detection, DNA computing, DNA hybridization
17Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour Combination can be hard: approximability of the unique coverage problem. Search on Bibsonomy SODA The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
17Alexandr Andoni, Piotr Indyk, Mihai Patrascu On the Optimality of the Dimensionality Reduction Method. Search on Bibsonomy FOCS The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
17Johan Håstad On Nontrivial Approximation of CSPs. Search on Bibsonomy APPROX-RANDOM The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
17Benny Applebaum, Yuval Ishai, Eyal Kushilevitz On Pseudorandom Generators with Linear Stretch in NC0. Search on Bibsonomy APPROX-RANDOM The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
17Uriel Feige, Elchanan Mossel, Dan Vilenchik Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. Search on Bibsonomy APPROX-RANDOM The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
17Subhash Khot Guest column: inapproximability results via Long Code based PCPs. Search on Bibsonomy SIGACT News The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
17Magnus Wahlström An Algorithm for the SAT Problem for Formulae of Linear Length. Search on Bibsonomy ESA The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
17Maurizio Patrignani Complexity Results for Three-Dimensional Orthogonal Graph Drawing. Search on Bibsonomy GD The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
17Iannis Tourlakis Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy. Search on Bibsonomy APPROX-RANDOM The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
17Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink Application of Mismatch Detection Methods in DNA Computing. Search on Bibsonomy DNA The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
17Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond An FPT Algorithm for Set Splitting. Search on Bibsonomy WG The full citation details ... 2003 DBLP  DOI  BibTeX  RDF
17Ryan Williams 0001 On Computing k-CNF Formula Properties. Search on Bibsonomy SAT The full citation details ... 2003 DBLP  DOI  BibTeX  RDF
17Emese Balogh, Attila Kuba, Alberto Del Lungo, Maurice Nivat Reconstruction of Binary Matrices from Absorbed Projections. Search on Bibsonomy DGCI The full citation details ... 2002 DBLP  DOI  BibTeX  RDF absorption, reconstruction, discrete tomography
17Peter J. Stuckey, Lei Zheng Improving GSAT Using 2SAT. Search on Bibsonomy CP The full citation details ... 2002 DBLP  DOI  BibTeX  RDF
17Uriel Feige Relations between average case complexity and approximation complexity. Search on Bibsonomy STOC The full citation details ... 2002 DBLP  DOI  BibTeX  RDF
17Kazuo Iwama, Suguru Tamaki Exploiting Partial Knowledge of Satisfying Assignments. Search on Bibsonomy WAE The full citation details ... 2001 DBLP  DOI  BibTeX  RDF
17Makoto Yokoo, Katsutoshi Hirayama The Effect of Nogood Learning in Distributed Constraint Satisfaction. Search on Bibsonomy ICDCS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF
17Venkatesan Guruswami Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Search on Bibsonomy APPROX The full citation details ... 2000 DBLP  DOI  BibTeX  RDF
17Limor Drori, David Peleg Faster Exact Solutions for Some NP-Hard Problems. Search on Bibsonomy ESA The full citation details ... 1999 DBLP  DOI  BibTeX  RDF
17Mario Szegedy Many-Valued Logics and Holographic Proofs. Search on Bibsonomy ICALP The full citation details ... 1999 DBLP  DOI  BibTeX  RDF
17Harry 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 FSTTCS The full citation details ... 1994 DBLP  DOI  BibTeX  RDF
17Peter Damaschke Induced Subgraph Isomorphism for Cographs in NP-Complete. Search on Bibsonomy WG The full citation details ... 1990 DBLP  DOI  BibTeX  RDF
Displaying result #1 - #88 of 88 (100 per page; Change: )
Valid XHTML 1.1! Valid CSS! [Valid RSS]
Maintained by L3S.
Previously maintained by Jörg Diederich.
Based upon DBLP by Michael Ley.
open data data released under the ODC-BY 1.0 license