Evgeny Dantsin

CoRR, 2024

2023

An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF.

[BibT_eX]

[DOI]

J. Satisf. Boolean Model. Comput., 2023

An AlphaZero-Inspired Approach to Solving Search Problems.

[BibT_eX]

[DOI]

Proceedings of the Decision Making Under Uncertainty and Constraints - A Why-Book, 2023

2022

An AlphaZero-Inspired Approach to Solving Search Problems.

[BibT_eX]

[DOI]

CoRR, 2022

2021

Worst-Case Upper Bounds.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Satisfiability - Second Edition, 2021

2020

Similarity Between Points in Metric Measure Spaces.

[BibT_eX]

[DOI]

Proceedings of the Similarity Search and Applications - 13th International Conference, 2020

2018

Reconstruction of Boolean Formulas in Conjunctive Normal Form.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 24th International Conference, 2018

2013

Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2011

Satisfiability Certificates Verifiable in Subexponential Time.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2011, 2011

2010

On Moderately Exponential Time for SAT.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

2009

Worst-Case Upper Bounds.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Satisfiability, 2009

2006

Population Variance under Interval Uncertainty: A New Algorithm.

[BibT_eX]

[DOI]

Reliab. Comput., 2006

A Faster Clause-Shortening Algorithm for SAT with No Restriction on Clause Length.

[BibT_eX]

[DOI]

J. Satisf. Boolean Model. Comput., 2006

MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in O(s2) Time.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2006

Quantum versions of k-CSP algorithms: a first step towards quantum algorithms for interval-related constraint satisfaction problems.

[BibT_eX]

[DOI]

Proceedings of the 2006 ACM Symposium on Applied Computing (SAC), 2006

2005

On quantum versions of record-breaking algorithms for SAT.

[BibT_eX]

[DOI]

SIGACT News, 2005

Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

An Improved Upper Bound for SAT

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

2004

Derandomization of Schuler's Algorithm for SAT

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

2003

A Robust Dna Computation Model That Captures Pspace.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2003

Algorithms for SAT based on search in Hamming balls

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Electron. Colloquium Comput. Complex., 2003

2002

A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search.

[BibT_eX]

[DOI]

Prabhakar Raghavan

Uwe Schöning

Theor. Comput. Sci., 2002

Solving Constraint Satisfaction Problems with DNA Computing.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

Algorithms for SAT and Upper Bounds on Their Complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Complexity and expressive power of logic programming.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2001

MAX SAT approximation beyond the limits of polynomial-time approximation.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2001

2000

Expressive Power and Data Complexity of Query Languages for Trees and Lists.

[BibT_eX]

[DOI]

Andrei Voronkov

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees.

[BibT_eX]

[DOI]

Andrei Voronkov

Proceedings of the Foundations of Software Science and Computation Structure, 1999

1997

Complexity of Query Answering in Logic Databases with Complex Values.

[BibT_eX]

[DOI]

Andrei Voronkov

Proceedings of the Logical Foundations of Computer Science, 4th International Symposium, 1997

1991

Probabilistic Logic Programs and their Semantics.

[BibT_eX]

[DOI]

Proceedings of the Logic Programming, First Russian Conference on Logic Programming, Irkutsk, Russia, September 14-18, 1990, 1991

1988

Algorithms for Probabilistic Inference.

[BibT_eX]

[DOI]