Evgeny Dantsin: Publications Available Online
- 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(2n)
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))n
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.
- 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 2nd
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 4th
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]
|
|