Staff profile

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