ALEXANDER B. WOLPERT, Ph.D.

Recent Publications

(starting 2003)

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 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]

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, 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, 2006. [pdf]

E. Dantsin, E.A. Hirsch, 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, 2006. Also ECCC, TR05-102, September 2005. [pdf]

E. Dantsin, V. Kreinovich, A. Wolpert. Quantum Versions of k-CSP Algorithms: a First Step Towards Quantum Algorithms for Interval-Related Constraint Satisfaction Problems. In Proceedings of the ACM Symposium on Applied Computing, SAC 2006, pages 1624-1628, 2006. [pdf]

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

E. Dantsin, V. Kreinovich, A. Wolpert. On Quantum Versions of Record-Breaking Algorithms for SAT. In SIGACT News, 36(4), pages 103-108, December 2005. [pdf]

E. Dantsin, A. Wolpert. A Faster Clause-Shortening Algorithm for SAT with No Restriction on Clause Length. In Journal on Satisfiability, Boolean Modeling and Computation, 1 (1), pages 49-60, August - December 2005. This paper is an extended version of the paper presented at SAT 2005 and published in LNCS 3569. [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, 2005. 
Also a different version of this paper appeared in ECCC, TR05-030, March 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. Also ECCC, TR04-017, March 2004 [ps

]

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, 2004. Also ECCC, TR03-072, October 2003. [ps]