Staff profile

Conference Paper

• Sherali-Adams and the binary encoding of combinatorial principles
  
  Dantchev, S., Ghani, A., & Martin, B. (2020). Sherali-Adams and the binary encoding of combinatorial principles. In Y. Kohayakawa & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (pp. 336-347). Springer Verlag. https://doi.org/10.1007/978-3-030-61792-9_27
• Resolution and the binary encoding of combinatorial principles
  
  Dantchev, S., Galesi, N., & Martin, B. (2019). Resolution and the binary encoding of combinatorial principles. In A. Shpilka (Ed.), 34th Computational Complexity Conference (CCC 2019). (pp. 6:1-6:25). Dagstuhl Publishing. https://doi.org/10.4230/lipics.ccc.2019.6
• Simplicial Complex Entropy
  
  Dantchev, S., & Ivrissimtzis, I. (2017). Simplicial Complex Entropy. In M. S. Floater, T. Lyche, M.-L. Mazure, K. Mørken, & L. L. Schumaker (Eds.), Mathematical methods for curves and surfaces : 9th International Conference, MMCS 2016, Tønsberg, Norway, June 23 - June 28, 2016. Revised selected papers. (pp. 96-107). Springer Verlag. https://doi.org/10.1007/978-3-319-67885-6_5
• Sublinear-Time Algorithms for Tournament Graphs
  
  Dantchev, S., Friedetzky, T., & Nagel, L. (2009). Sublinear-Time Algorithms for Tournament Graphs. In H. Q. Ngo (Ed.), Computing and combinatorics : 15th Annual International Conference, COCOON 2009, 13-15 July 2009, Niagara Falls, NY, USA ; proceedings. (pp. 459-471). Springer Verlag. https://doi.org/10.1007/978-3-642-02882-3_46
• Parameterized proof complexity
  
  Dantchev, S., Martin, B., & Szeider, S. (2007). Parameterized proof complexity. In 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, 21-23 October 2007, Providence, RI ; proceedings. (pp. 150-160). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2007.53
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
  
  Dantchev, S. (2007). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. In STOC ’07 : proceedings of the 39th Annual ACM Symposium on Theory of Computing : San Diego, California, USA, June 11-13, 2007. (pp. 311-317). Association for Computing Machinery (ACM). https://doi.org/10.1145/1250790.1250837
• Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems
  
  Dantchev, S., & Madelaine, F. (2006). Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems. In D. Grigoriev, J. Harrison, & E. A. Hirsch (Eds.), Lecture Notes in Computer Science (pp. 159-170). https://doi.org/10.1007/11753728_18
• 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). On relativisation and complexity gap for resolution-based proof systems. In Computer science logic : 17th International Workshop CSL 2003, 12th Annual Conference of the EACSL, 8th Kurt Gödel Colloquium, KGC 2003, 25-30 August 2003, Vienna, Austria ; proceedings (pp. 142-154). Springer Verlag. https://doi.org/10.1007/978-3-540-45220-1_14
• 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). Planar tautologies hard for resolution. In 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada ; proceedings. (pp. 220-229). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/sfcs.2001.959896
• Tree resolution proofs of the weak pigeon-hole principle
  
  Dantchev, S., & Riis, S. (2001). Tree resolution proofs of the weak pigeon-hole principle. In 16th Annual IEEE Conference on Computational Complexity, 18-21 June 2001, Chicago, Illinois ; proceedings. (pp. 69-77). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ccc.2001.933873

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