Staff profile
Overview
https://apps.dur.ac.uk/biography/image/1188
Affiliation | Telephone |
---|---|
Assistant Professor in the Department of Computer Science |
Publications
Conference Paper
- Sherali-Adams and the binary encoding of combinatorial principles
Dantchev, S., Ghani, A., & Martin, B. (2020, May). Sherali-Adams and the binary encoding of combinatorial principles. Presented at LATIN 2020, São Paulo, Brazil - Resolution and the binary encoding of combinatorial principles
Dantchev, S., Galesi, N., & Martin, B. (2019, July). Resolution and the binary encoding of combinatorial principles. Presented at Computational Complexity Conference, New Brunswick, New Jersey, USA - Simplicial Complex Entropy
Dantchev, S., & Ivrissimtzis, I. (2016, June). Simplicial Complex Entropy. Presented at 9th International Conference on Mathematical Methods for Curves and Surfaces, Tønsberg, Norway - Sublinear-Time Algorithms for Tournament Graphs
Dantchev, S., Friedetzky, T., & Nagel, L. (2009, July). Sublinear-Time Algorithms for Tournament Graphs. Presented at 15th Annual International Conference of Computing and Combinatorics (COCOON 2009), Niagara Falls, New York, USA - Parameterized proof complexity
Dantchev, S., Martin, B., & Szeider, S. (2007, October). Parameterized proof complexity. Presented at 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, USA - Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Dantchev, S. (2007, June). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Presented at 39th Annual ACM Symposium on Theory of Computing, San Diego, CA - Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems
Dantchev, S., & Madelaine, F. (2006, December). Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems. Presented at International Computer Science Symposium in Russia., St. Peterburg, Russia - On the Computational Limits of Infinite Satisfaction.
Dantchev, S., & Valencia, F. (2005, March). On the Computational Limits of Infinite Satisfaction. Presented at The 20th Annual ACM Symposium on Applied Computing, Santa Fe, USA - On relativisation and complexity gap for resolution-based proof systems
Dantchev, S., & Riis, S. (2003, August). On relativisation and complexity gap for resolution-based proof systems. Presented at 12th Annual Conference of the EACSL Computer Science Logic., Vienna, Austria - Width-Size Trade-offs for the Pigeon-Hole Principle.
Dantchev, S. (2002, May). Width-Size Trade-offs for the Pigeon-Hole Principle. Presented at The 17th Annual Conference on Computational Complexity, Montreal, Canada - Planar tautologies hard for resolution
Dantchev, S., & Riis, S. (2001, October). Planar tautologies hard for resolution. Presented at 42nd IEEE Symposium of Foundations of Computer Science, Las Vegas, Nev - Tree resolution proofs of the weak pigeon-hole principle
Dantchev, S., & Riis, S. (2001, June). Tree resolution proofs of the weak pigeon-hole principle. Presented at 16th Annual IEEE Conference on Computational Complexity, Chicago, Ill
Journal Article
- Combinatorial Axiomatisation of Edge-weighted PageRank
Dantchev, S., & Heppenstall, A. (in press). Combinatorial Axiomatisation of Edge-weighted PageRank. Internet mathematics, - Proof Complexity and the Binary Encoding of Combinatorial Principles
Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Proof Complexity and the Binary Encoding of Combinatorial Principles. SIAM Journal on Computing, 53(3), 764-802. https://doi.org/10.1137/20m134784x - Depth lower bounds in Stabbing Planes for combinatorial principles
Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Depth lower bounds in Stabbing Planes for combinatorial principles. Logical Methods in Computer Science, 20(1), 1-19. https://doi.org/10.46298/lmcs-20%281%3A1%292024 - The Riis Complexity Gap for QBF Resolution
Beyersdorff, O., Clymo, J., Dantchev, S., & Martin, B. (2024). The Riis Complexity Gap for QBF Resolution. Journal on Satisfiability, Boolean Modeling and Computation, 15(1), 9-25. https://doi.org/10.3233/sat-231505 - Relativization makes contradictions harder for Resolution
Dantchev, S., & Martin, B. (2014). Relativization makes contradictions harder for Resolution. Annals of Pure and Applied Logic, 165(3), 837-857. https://doi.org/10.1016/j.apal.2013.10.009 - Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Dantchev, S., & Martin, B. (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity, 22(1), 191-213. https://doi.org/10.1007/s00037-012-0049-1 - Cutting Planes and the Parameter Cutwidth
Dantchev, S., & Martin, B. (2012). Cutting Planes and the Parameter Cutwidth. Theory of Computing Systems, 51(1), 50-64. https://doi.org/10.1007/s00224-011-9373-0 - The limits of tractability in Resolution-based propositional proof systems
Dantchev, S., & Martin, B. (2012). The limits of tractability in Resolution-based propositional proof systems. Annals of Pure and Applied Logic, 163(3), 656-668. https://doi.org/10.1016/j.apal.2011.11.001 - Sublinear-time algorithms for tournament graphs
Dantchev, S., Friedetzky, T., & Nagel, L. (2011). Sublinear-time algorithms for tournament graphs. Journal of Combinatorial Optimization, 22, 469–481. https://doi.org/10.1007/s10878-010-9325-7 - Dynamic Neighbourhood Cellular Automata
Dantchev, S. (2011). Dynamic Neighbourhood Cellular Automata. The Computer Journal, 54(1), 26-30. https://doi.org/10.1093/comjnl/bxp019 - Parameterized Proof Complexity
Dantchev, S., Martin, B., & Szeider, S. (2011). Parameterized Proof Complexity. Computational Complexity, 20(1), 51-85. https://doi.org/10.1007/s00037-010-0001-1 - Tight rank lower bounds for the Sherali–Adams proof system
Dantchev, S., Martin, B., & Rhodes, M. (2009). Tight rank lower bounds for the Sherali–Adams proof system. Theoretical Computer Science, 410(21-23), 2054-2063. https://doi.org/10.1016/j.tcs.2009.01.002 - Improved sorting-based procedure for integer programming
Dantchev, S. (2002). Improved sorting-based procedure for integer programming. Mathematical Programming, 92(2), 297-300. https://doi.org/10.1007/s101070100245