- Evgeny Dantsin and Alexander Wolpert. Exponential complexity of
satisfiability testing for linear-size Boolean formulas. In
*Proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013*, volume 7878 of*Lecture Notes in Computer Science*, pages 110-121. Springer, 2013. [pdf] - Evgeny Dantsin and Edward A. Hirsch. Satisfiability certificates
verifiable in subexponential time. In
*Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011*, volume 6695 of*Lecture Notes in Computer Science*, pages 19-32. Springer, 2011. [pdf] - Evgeny Dantsin. Maximum satisfiability and subexponential time.
In S. Feferman and W. Sieg, editors,
*Proofs, Categories and Computations: Essays in Honor of Grigori Mints*, pages 81-92. College Publications, 2010. - Evgeny Dantsin and Alexander Wolpert. On moderately exponential
time for SAT. In
*Proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010*, volume 6175 of*Lecture Notes in Computer Science*, pages 313-325. Springer, 2010. [pdf] - Evgeny Dantsin and Edward A. Hirsch. Worst-case upper bounds. In
*Handbook of Satisfiability*, chapter 12, pages 403-424. IOS Press, 2009. [link] [pdf] - Evgeny Dantsin and Alexander Wolpert. MAX-SAT for formulas with
constant clause density can be solved faster than in
*O*(2) time. In^{n}*Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, SAT 2006*, volume 4121 of*Lecture Notes in Computer Science*, pages 266-276. Springer, 2006. [pdf] - Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert, and Gang
Xiang. Population variance under interval uncertainty: A new algorithm.
*Reliable Computing*, 12(4):273-280, 2006. [pdf] - Martine Ceberio, Evgeny Dantsin, Vladik Kreinovich, Alexander
Wolpert, and Gang Xiang. Detecting outliers under interval uncertainty:
A new algorithm based on constraint satisfaction. In
*Proceedings of the 11th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2006*, pages 802-809, 2006. [pdf] - Evgeny Dantsin, Edward A. Hirsch, and Alexander Wolpert. Clause
shortening combined with pruning yields a new upper bound for
deterministic SAT algorithms. In
*Proceedings of the 6th International Conference on Algorithms and Complexity, CIAC 2006*, volume 3998 of*Lecture Notes in Computer Science*, pages 60-68. Springer, 2006. [pdf] - Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert. Quantum
versions of
*k*-CSP algorithms: A first step towards quantum algorithms for interval-related constraint satisfaction problems. In*Proceedings of the 21st Annual ACM Symposium on Applied Computing, SAC 2006*, pages 1624-1628, 2006. [pdf] - Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert. On
quantum versions of record-breaking algorithms for SAT.
*ACM SIGACT News*, 36(4):103-108, 2005. [pdf] - Evgeny Dantsin and Alexander Wolpert. A faster clause-shortening
algorithm for SAT with no restriction on clause length.
*Journal on Satisfiability, Boolean Modeling, and Computation*, 1:49-60, 2005. [pdf] - Evgeny Dantsin and Alexander Wolpert. An improved upper bound for
SAT. In
*Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing, SAT 2005*, volume 3569 of*Lecture Notes in Computer Science*, pages 400-407. Springer, 2005. [pdf] - Evgeny Dantsin and Alexander Wolpert. Derandomization of
Schuler's algorithm for SAT. In
*Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, SAT 2004*, volume 3542 of*Lecture Notes in Computer Science*, pages 80-88. Springer, 2005. [pdf] - Evgeny Dantsin, Edward A. Hirsch, and Alexander Wolpert.
Algorithms for SAT based on search in Hamming balls. In
*Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004*, volume 2996 of*Lecture Notes in Computer Science*, pages 141-151. Springer, 2004. [pdf] - Evgeny Dantsin and Alexander Wolpert. A robust DNA computation
model that captures PSPACE.
*International Journal of Foundations of Computer Science*, 14(5):933-951, 2003. [ps] - Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravindran
Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and
Uwe SchÃ¶ning. A deterministic (2-2/(
*k*+1))algorithm for^{n}*k*-SAT based on local search.*Theoretical Computer Science*, 289(1):69-83, 2002. [pdf] - Evgeny Dantsin and Alexander Wolpert. Solving constraint
satisfaction problems with DNA computing. In
*Proceedings of the 8th Annual International Computing and Combinatorics Conference, COCOON 2002*, volume 2387 of*Lecture Notes in Computer Science*, pages 171-180. Springer, 2002. [pdf] - Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, and Boris
Konev. MAX SAT approximation beyond the limits of polynomial-time
approximation.
*Annals of Pure and Applied Logic*, 113(1-3):81-94, 2001. [pdf] - Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov.
Complexity and expressive power of logic programming.
*ACM Computing Surveys*, 33(3):374-425, 2001. [pdf] - Evgeny Dantsin, Edward A. Hirsch, Sergei Ivanov, and Maxim
Vsemirnov. Algorithms for SAT and upper bounds on their complexity.
*Zapiski Nauchnykh Seminarov POMI*, 277:14-46, 2001. In Russian. [ps] English translation:*Journal of Mathematical Sciences*, 118(2):4948-4962, 2003. [pdf] - Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, and Uwe
SchÃ¶ning. Deterministic algorithms for
*k*-SAT based on covering codes and local search. In*Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP 2000*, volume 1853 of*Lecture Notes in Computer Science*, pages 236-247. Springer, 2000. [pdf] - Evgeny Dantsin and Andrei Voronkov. Expressive power and data
complexity of nonrecursive query languages for lists and trees. In
*Proceedings of the 19th ACM Symposium on Principles of Database Systems, PODS 2000*, pages 157-165. ACM, 2000. [ps] - Evgeny Dantsin and Andrei Voronkov. A nondeterministic
polynomial-time unification algorithm for bags, sets and trees. In
*Proceedings of the 2nd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 1999*, volume 1578 of*Lecture Notes in Computer Science*, pages 180-196. Springer, 1999. [ps] - Evgeny Dantsin and Andrei Voronkov. Complexity of query answering
in logic databases with complex value. In
*Proceedings of the 4th International Symposium on Logical Foundations of Computer Science, LFCS 1997*, volume 1234 of*Lecture Notes in Computer Science*, pages 56-66. Springer, 1997. [ps]

Back to Evgeny Dantsin's home page