Evgeny Dantsin: Publications Available Online

Boolean Satisfiability

• Evgeny Dantsin and Edward A. Hirsch. Worst-case upper bounds. In Handbook of Satisfiability, chapter 12, pages 403–424. IOS Press, 2009. [link]
• Evgeny Dantsin and Alexander Wolpert. MAX-SAT for formulas with constant clause density can be solved faster than in O(2ⁿ) time. In 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, August 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, May 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, December 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, November 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, June 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, March 2004. [pdf]
• 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 k-SAT based on local search. Theoretical Computer Science, 289(1):69–83, October 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, December 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, November 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, July 2000. [pdf]

Logic Query Languages

• Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374–425, September 2001. [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, May 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, March 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, July 1997. [ps]

Other Topics

• Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert, and Gang Xiang. Population variance under interval uncertainty: A new algorithm. Reliable Computing, 12(4):273–280, August 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, July 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, April 2006. [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, October 2003. [ps]
• 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, August 2002. [pdf]

Back to Evgeny Dantsin's home page