Evgeny Dantsin: Publications Available Online

Boolean satisfiability

E. Dantsin and E. A. Hirsch. Worst-case upper bounds. In Handbook of Satisfiability, chapter 12, pages 403–424. IOS Press, 2009. [link]

 

E. Dantsin and A. 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]

 

E. Dantsin, E. A. Hirsch, and A. 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]

 

E. Dantsin, V. Kreinovich, and A. Wolpert. On quantum versions of record-breaking algorithms for SAT. ACM SIGACT News, 36(4):103–108, December 2005. [pdf]

 

E. Dantsin and A. 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]

 

E. Dantsin and A. 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]

 

E. Dantsin and A. 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]

 

E. Dantsin, E. A. Hirsch, and A. 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]

 

E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, and U. 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]

 

E. Dantsin, M. Gavrilovich, E. A. Hirsch, and B. 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]

 

E. Dantsin, E. A. Hirsch, S. Ivanov, and M. 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]. (Preliminary version appeared as ECCC TR01-012.)

 

E. Dantsin, A. Goerdt, E. A. Hirsch, and U. 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]. This paper received the Best ICALP Paper Award.

Logic query languages

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374-425, September 2001. [pdf]

 

E. Dantsin and A. 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. [pdf]

 

E. Dantsin and A. Voronkov. A nondeterministic polynomial-time unification algorithm for bags, sets and trees. In Proceedings of the 2^nd International Conference on Foundations of Software Science and Computation Structures, FOSSACS’99, volume 1578 of Lecture Notes in Computer Science, pages 180–196. Springer, March 1999. [ps]

 

E. Dantsin and A. Voronkov. Complexity of query answering in logic databases with complex value. In Proceedings of the 4^th International Symposium on Logical Foundations of Computer Science, LFCS’97, volume 1234 of Lecture Notes in Computer Science, pages 56–66. Springer, July 1997. [ps]

Other topics

E. Dantsin, V. Kreinovich, A. Wolpert, and G. Xiang. Population variance under interval uncertainty: A new algorithm. Reliable Computing, 12(4):273-280, August 2006. [pdf]

 

M. Ceberio, E. Dantsin, V. Kreinovich, A. Wolpert, and G. 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]

 

E. Dantsin, V. Kreinovich, and A. 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]

 

E. Dantsin and A. Wolpert. A robust DNA computation model that captures PSPACE. International Journal Of Foundations of Computer Science, 14(5):933-951, October 2003. [ps]

 

E. Dantsin and A. 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]