Evgeny Dantsin

According to our database, Evgeny Dantsin authored at least 31 papers between 1988 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

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

Evgeny Dantsin, Alexander Wolpert

J. Satisf. Boolean Model. Comput., 2023

An AlphaZero-Inspired Approach to Solving Search Problems.

Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert

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

2022

An AlphaZero-Inspired Approach to Solving Search Problems.

Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert

CoRR, 2022

2021

Worst-Case Upper Bounds.

Evgeny Dantsin, Edward A. Hirsch

Proceedings of the Handbook of Satisfiability - Second Edition, 2021

2020

Similarity Between Points in Metric Measure Spaces.

Evgeny Dantsin, Alexander Wolpert

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

2018

Reconstruction of Boolean Formulas in Conjunctive Normal Form.

Evgeny Dantsin, Alexander Wolpert

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

2013

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

Evgeny Dantsin, Alexander Wolpert

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

2011

Satisfiability Certificates Verifiable in Subexponential Time.

Evgeny Dantsin, Edward A. Hirsch

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

2010

On Moderately Exponential Time for SAT.

Evgeny Dantsin, Alexander Wolpert

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

2009

Worst-Case Upper Bounds.

Evgeny Dantsin, Edward A. Hirsch

Proceedings of the Handbook of Satisfiability, 2009

2006

Population Variance under Interval Uncertainty: A New Algorithm.

Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert, Gang Xiang

Reliab. Comput., 2006

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

Evgeny Dantsin, Alexander Wolpert

J. Satisf. Boolean Model. Comput., 2006

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

Evgeny Dantsin, Alexander Wolpert

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.

Evgeny Dantsin, Alexander Wolpert, Vladik Kreinovich

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

2005

On quantum versions of record-breaking algorithms for SAT.

Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert

SIGACT News, 2005

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

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Electron. Colloquium Comput. Complex., 2005

An Improved Upper Bound for SAT

Evgeny Dantsin, Alexander Wolpert

Electron. Colloquium Comput. Complex., 2005

2004

Derandomization of Schuler's Algorithm for SAT

Evgeny Dantsin, Alexander Wolpert

Electron. Colloquium Comput. Complex., 2004

2003

A Robust Dna Computation Model That Captures Pspace.

Evgeny Dantsin, Alexander Wolpert

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

Algorithms for SAT based on search in Hamming balls

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

Electron. Colloquium Comput. Complex., 2003

2002

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

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning

Theor. Comput. Sci., 2002

Solving Constraint Satisfaction Problems with DNA Computing.

Evgeny Dantsin, Alexander Wolpert

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

2001

Algorithms for SAT and Upper Bounds on Their Complexity

Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, Maxim Vsemirnov

Electron. Colloquium Comput. Complex., 2001

Complexity and expressive power of logic programming.

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov

ACM Comput. Surv., 2001

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

Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev

Ann. Pure Appl. Log., 2001

2000

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

Evgeny Dantsin, Andrei Voronkov

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

Deterministic Algorithms for <i>k</i>-SAT Based on Covering Codes and Local Search.

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning

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

1999

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

Evgeny Dantsin, Andrei Voronkov

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

1997

Complexity of Query Answering in Logic Databases with Complex Values.

Evgeny Dantsin, Andrei Voronkov

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

1991

Probabilistic Logic Programs and their Semantics.

Evgeny Dantsin

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

1988

Algorithms for Probabilistic Inference.

Evgeny Dantsin

Proceedings of the COLOG-88, 1988