Search results for "3Sat"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Dominique Attali, André Lieutier	Optimal reconstruction might be hard.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	3SAT, homological simplification, sampling conditions, topological persistence, NP-completeness, shape reconstruction
2	Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor	The Power of Unentanglement.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
2	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
2	Michael de Mare, Rebecca N. Wright	Secure Set Membership Using 3Sat.	ICICS	2006	DBLP DOI BibTeX RDF
2	Venkatesan Guruswami, Subhash Khot	Hardness of Max 3SAT with No Mixed Clauses.	IEEE Conference on Computational Complexity	2005	DBLP DOI BibTeX RDF
2	Rani Siromoney, Bireswar Das	Plasmids to Solve #3SAT.	Aspects of Molecular Computing	2004	DBLP DOI BibTeX RDF
2	Uriel Feige	Relations between Average Case Complexity and Approximation Complexity. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	random 3sat, bipartite clique, bisection
2	Mitsuo Motoki	Random Instance Generation for MAX 3SAT.	COCOON	2001	DBLP DOI BibTeX RDF
2	Howard J. Karloff, Uri Zwick	A 7/8-Approximation Algorithm for MAX 3SAT?	FOCS	1997	DBLP DOI BibTeX RDF
2	Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay	DNA Models and Algorithms for NP-complete Problems. (PDF / PS)	IEEE Conference on Computational Complexity	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
1	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
1	A. Garcia-Saez, J. I. Latorre	An exact tensor network for the 3SAT problem	CoRR	2011	DBLP BibTeX RDF
1	Vicky Choi	Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems	CoRR	2010	DBLP BibTeX RDF
1	Vicky Choi	Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems	CoRR	2010	DBLP BibTeX RDF
1	Peiyush Jain	On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem	CoRR	2010	DBLP BibTeX RDF
1	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
1	Luigi Salemi	Method of resolution of 3SAT in polynomial time	CoRR	2009	DBLP BibTeX RDF
1	Lusheng Wang, Binhai Zhu	On the Tractability of Maximal Strip Recovery.	TAMC	2009	DBLP DOI BibTeX RDF
1	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
1	Tianyan Deng, Daoyun Xu	Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems.	ICYCS	2008	DBLP DOI BibTeX RDF
1	Peter Gregory, Maria Fox, Derek Long	A New Empirical Study of Weak Backdoors.	CP	2008	DBLP DOI BibTeX RDF
1	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
1	Wenceslas Fernandez de la Vega, Marek Karpinski	1.0957-Approximation Algorithm for Random MAX-3SAT.	RAIRO - Operations Research	2007	DBLP DOI BibTeX RDF
1	David Nistér, Fredrik Kahl, Henrik Stewénius	Structure from Motion with Missing Data is NP-Hard.	ICCV	2007	DBLP DOI BibTeX RDF
1	B. Subramaniam, Rani Siromoney	Contextial Insertion for #3SAT.	Bulletin of the EATCS	2006	DBLP BibTeX RDF
1	Honglei Zeng, Sheila A. McIlraith	Experimental Results on the Satisfiable Core in Random 3SAT.	ISAIM	2006	DBLP BibTeX RDF
1	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
1	Michael Krivelevich, Dan Vilenchik	Solving random satisfiable 3CNF formulas in expected polynomial time.	SODA	2006	DBLP DOI BibTeX RDF
1	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
1	Alexandr Andoni, Piotr Indyk, Mihai Patrascu	On the Optimality of the Dimensionality Reduction Method.	FOCS	2006	DBLP DOI BibTeX RDF
1	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Uriel Feige, Elchanan Mossel, Dan Vilenchik	Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Johan Håstad	On Nontrivial Approximation of CSPs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink	Application of Mismatch Detection Methods in DNA Computing.	Natural Computing	2006	DBLP DOI BibTeX RDF	mismatch detection, mutation detection, DNA computing, DNA hybridization
1	Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström	Counting models for 2SAT and 3SAT formulae.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
1	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
1	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
1	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Magnus Wahlström	An Algorithm for the SAT Problem for Formulae of Linear Length.	ESA	2005	DBLP DOI BibTeX RDF
1	Maurizio Patrignani	Complexity Results for Three-Dimensional Orthogonal Graph Drawing.	Graph Drawing	2005	DBLP DOI BibTeX RDF
1	Piotr Berman, Marek Karpinski, Alexander D. Scott	Computational Complexity of Some Restricted Instances of 3SAT	Electronic Colloquium on Computational Complexity (ECCC)	2004	DBLP BibTeX RDF
1	Christiaan V. Henkel, Grzegorz Rozenberg, Herman P. Spaink	Application of Mismatch Detection Methods in DNA Computing.	DNA	2004	DBLP DOI BibTeX RDF
1	Piotr Berman, Marek Karpinski, Alex D. Scott	Approximation Hardness of Short Symmetric Instances of MAX-3SAT	Electronic Colloquium on Computational Complexity (ECCC)	2003	DBLP BibTeX RDF
1	Ryan Williams	On Computing k-CNF Formula Properties.	SAT	2003	DBLP DOI BibTeX RDF
1	Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond	An FPT Algorithm for Set Splitting.	WG	2003	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.	Algorithmica	2003	DBLP DOI BibTeX RDF	Set splitting, Hardness of approximations, PCP, Gadgets
1	Wenceslas Fernandez de la Vega, Marek Karpinski	9/8-Approximation Algorithm for Random MAX-3SAT	Electronic Colloquium on Computational Complexity (ECCC)	2002	DBLP BibTeX RDF
1	Uriel Feige	Relations between average case complexity and approximation complexity.	STOC	2002	DBLP DOI BibTeX RDF
1	Peter J. Stuckey, Lei Zheng	Improving GSAT Using 2SAT.	CP	2002	DBLP BibTeX RDF
1	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
1	Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe	The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.	Theory Comput. Syst.	2002	DBLP DOI BibTeX RDF
1	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
1	Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe	On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.	STACS	2001	DBLP DOI BibTeX RDF
1	Kazuo Iwama, Suguru Tamaki	Exploiting Partial Knowledge of Satisfying Assignments.	Algorithm Engineering	2001	DBLP DOI BibTeX RDF
1	Makoto Yokoo, Katsutoshi Hirayama	The Effect of Nogood Learning in Distributed Constraint Satisfaction.	ICDCS	2000	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	Inapproximability results for set splitting and satisfiability problems with no mixed clauses.	APPROX	2000	DBLP DOI BibTeX RDF
1	Limor Drori, David Peleg	Faster Exact Solutions for Some NP-Hard Problems.	ESA	1999	DBLP DOI BibTeX RDF
1	Mario Szegedy	Many-Valued Logics and Holographic Proofs.	ICALP	1999	DBLP DOI BibTeX RDF
1	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
1	Tuomas Sandholm	A Second Order Parameter for 3SAT.	AAAI/IAAI, Vol. 1	1996	DBLP BibTeX RDF
1	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
1	Peter Damaschke	Induced Subgraph Isomorphism for Cographs in NP-Complete.	WG	1990	DBLP DOI BibTeX RDF