Search results for "3SAT"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
93	Venkatesan Guruswami, Subhash Khot	Hardness of Max 3SAT with No Mixed Clauses.	CCC	2005	DBLP DOI BibTeX RDF
83	Michael Krivelevich, Dan Vilenchik	Solving random satisfiable 3CNF formulas in expected polynomial time.	SODA	2006	DBLP DOI BibTeX RDF
76	Rani Siromoney, Bireswar Das	Plasmids to Solve #3SAT.	Aspects of Molecular Computing	2004	DBLP DOI BibTeX RDF
76	Howard J. Karloff, Uri Zwick	A 7/8-Approximation Algorithm for MAX 3SAT?	FOCS	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.	FOCI	2007	DBLP DOI BibTeX RDF
60	Michael de Mare, Rebecca N. Wright	Secure Set Membership Using 3Sat.	ICICS	2006	DBLP DOI BibTeX RDF
60	Mitsuo Motoki	Random Instance Generation for MAX 3SAT.	COCOON	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.	Theory Comput. Syst.	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.	STACS	2001	DBLP DOI BibTeX RDF
46	Dominique Attali, André Lieutier	Optimal reconstruction might be hard.	SCG	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.	CCC	2008	DBLP DOI BibTeX RDF	QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
46	Uriel Feige	Relations between Average Case Complexity and Approximation Complexity.	CCC	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.	CCC	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.	FOCS	2008	DBLP DOI BibTeX RDF
33	Tianyan Deng, Daoyun Xu	Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems.	ICYCS	2008	DBLP DOI BibTeX RDF
33	Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb	Private approximation of search problems.	STOC	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.	STOC	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.	Algorithmica	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.	STOC	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).	WG	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.	EvoStar	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.	CoRR	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.	GECCO Companion	2023	DBLP DOI BibTeX RDF
27	Samuel Deleplanque	Solving 3SAT and MIS Problems with Analog Quantum Machines.	ICCSA (Workshops 1)	2023	DBLP DOI BibTeX RDF
27	Tong Qin, Osamu Watanabe	An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem.	IEICE Trans. Inf. Syst.	2022	DBLP DOI BibTeX RDF
27	Shyan Akmal, R. Ryan Williams	MAJORITY-3SAT (and Related Problems) in Polynomial Time.	CoRR	2021	DBLP BibTeX RDF
27	Shyan Akmal, Ryan Williams 0001	MAJORITY-3SAT (and Related Problems) in Polynomial Time.	FOCS	2021	DBLP DOI BibTeX RDF
27	Chuzo Iwamoto, Tatsuaki Ibusuki	Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles.	IEICE Trans. Inf. Syst.	2020	DBLP BibTeX RDF
27	Tong Qin 0003, Osamu Watanabe 0001	An improvement of the algorithm of Hertli for the unique 3SAT problem.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
27	Latif Salum	Tractability of One-in-three 3SAT: P = NP.	CoRR	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.	CoRR	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.	SODA	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.	CoRR	2018	DBLP BibTeX RDF
27	Matthew Delacorte	Solving 3SAT By Reduction To Testing For Odd Hole.	CoRR	2018	DBLP BibTeX RDF
27	Tong Qin 0003, Osamu Watanabe 0001	An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem.	WALCOM	2018	DBLP DOI BibTeX RDF
27	Tong Qin 0003, Osamu Watanabe 0001	An improvement of the algorithm of Hertli for the unique 3SAT problem.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
27	Cristian Dumitrescu	A randomized, efficient algorithm for 3SAT.	CoRR	2017	DBLP BibTeX RDF
27	Byoungkwon An, Erik D. Demaine, Martin L. Demaine, Jason S. Ku	Computing 3SAT on a Fold-and-Cut Machine.	CCCG	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.	QTOP@NetSys	2017	DBLP DOI BibTeX RDF
27	Irit Dinur	Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
27	Lidong Wu	On strongly planar 3SAT.	J. Comb. Optim.	2016	DBLP DOI BibTeX RDF
27	Ali Dehghan 0001	On strongly planar not-all-equal 3SAT.	J. Comb. Optim.	2016	DBLP DOI BibTeX RDF
27	Koh-ichi Nagao	Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system.	IACR Cryptol. ePrint Arch.	2015	DBLP BibTeX RDF
27	Iddo Tzameret	On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
27	Iddo Tzameret	On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation	CoRR	2013	DBLP BibTeX RDF
27	Artur García-Sáez, José Ignacio Latorre	An exact tensor network for the 3SAT problem.	Quantum Inf. Comput.	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.	Algorithms	2012	DBLP DOI BibTeX RDF
27	Artur García-Sáez, José Ignacio Latorre	An exact tensor network for the 3SAT problem	CoRR	2011	DBLP BibTeX RDF
27	Vicky Choi	Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems	CoRR	2010	DBLP BibTeX RDF
27	Vicky Choi	Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems	CoRR	2010	DBLP BibTeX RDF
27	Peiyush Jain	On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem	CoRR	2010	DBLP BibTeX RDF
27	Luigi Salemi	Method of resolution of 3SAT in polynomial time	CoRR	2009	DBLP BibTeX RDF
27	Wenceslas Fernandez de la Vega, Marek Karpinski	1.0957-Approximation Algorithm for Random MAX-3SAT.	RAIRO Oper. Res.	2007	DBLP DOI BibTeX RDF
27	B. Subramaniam, Rani Siromoney	Contextial Insertion for #3SAT.	Bull. EATCS	2006	DBLP BibTeX RDF
27	Honglei Zeng, Sheila A. McIlraith	Experimental Results on the Satisfiable Core in Random 3SAT.	AI&M	2006	DBLP BibTeX RDF
27	Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström	Counting models for 2SAT and 3SAT formulae.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
27	Piotr Berman, Marek Karpinski, Alexander D. Scott	Computational Complexity of Some Restricted Instances of 3SAT	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
27	Piotr Berman, Marek Karpinski, Alex D. Scott	Approximation Hardness of Short Symmetric Instances of MAX-3SAT.	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
27	Wenceslas Fernandez de la Vega, Marek Karpinski	9/8-Approximation Algorithm for Random MAX-3SAT	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
27	Tuomas Sandholm	A Second Order Parameter for 3SAT.	AAAI/IAAI, Vol. 1	1996	DBLP BibTeX RDF
17	Dániel Marx	Tractable hypergraph properties for constraint satisfaction and conjunctive queries.	STOC	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.	TAMC	2009	DBLP DOI BibTeX RDF
17	Tianyan Deng, Daoyun Xu	NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k).	FAW	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.	CP	2008	DBLP DOI BibTeX RDF
17	David Nistér, Fredrik Kahl, Henrik Stewénius	Structure from Motion with Missing Data is NP-Hard.	ICCV	2007	DBLP DOI BibTeX RDF
17	Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink	Application of Mismatch Detection Methods in DNA Computing.	Nat. Comput.	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.	SODA	2006	DBLP DOI BibTeX RDF
17	Alexandr Andoni, Piotr Indyk, Mihai Patrascu	On the Optimality of the Dimensionality Reduction Method.	FOCS	2006	DBLP DOI BibTeX RDF
17	Johan Håstad	On Nontrivial Approximation of CSPs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
17	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
17	Uriel Feige, Elchanan Mossel, Dan Vilenchik	Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
17	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
17	Magnus Wahlström	An Algorithm for the SAT Problem for Formulae of Linear Length.	ESA	2005	DBLP DOI BibTeX RDF
17	Maurizio Patrignani	Complexity Results for Three-Dimensional Orthogonal Graph Drawing.	GD	2005	DBLP DOI BibTeX RDF
17	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
17	Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink	Application of Mismatch Detection Methods in DNA Computing.	DNA	2004	DBLP DOI BibTeX RDF
17	Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond	An FPT Algorithm for Set Splitting.	WG	2003	DBLP DOI BibTeX RDF
17	Ryan Williams 0001	On Computing k-CNF Formula Properties.	SAT	2003	DBLP DOI BibTeX RDF
17	Emese Balogh, Attila Kuba, Alberto Del Lungo, Maurice Nivat	Reconstruction of Binary Matrices from Absorbed Projections.	DGCI	2002	DBLP DOI BibTeX RDF	absorption, reconstruction, discrete tomography
17	Peter J. Stuckey, Lei Zheng	Improving GSAT Using 2SAT.	CP	2002	DBLP DOI BibTeX RDF
17	Uriel Feige	Relations between average case complexity and approximation complexity.	STOC	2002	DBLP DOI BibTeX RDF
17	Kazuo Iwama, Suguru Tamaki	Exploiting Partial Knowledge of Satisfying Assignments.	WAE	2001	DBLP DOI BibTeX RDF
17	Makoto Yokoo, Katsutoshi Hirayama	The Effect of Nogood Learning in Distributed Constraint Satisfaction.	ICDCS	2000	DBLP DOI BibTeX RDF
17	Venkatesan Guruswami	Inapproximability results for set splitting and satisfiability problems with no mixed clauses.	APPROX	2000	DBLP DOI BibTeX RDF
17	Limor Drori, David Peleg	Faster Exact Solutions for Some NP-Hard Problems.	ESA	1999	DBLP DOI BibTeX RDF
17	Mario Szegedy	Many-Valued Logics and Holographic Proofs.	ICALP	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.	FSTTCS	1994	DBLP DOI BibTeX RDF
17	Peter Damaschke	Induced Subgraph Isomorphism for Cographs in NP-Complete.	WG	1990	DBLP DOI BibTeX RDF