3 papers
cs.LO2019
Sherali-Adams and the binary encoding of combinatorial principles
Stefan Dantchev, Abdul Ghani, Barnaby Martin
We consider the Sherali-Adams (SA) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Princip…
cs.CC2018
Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in -- an extension of Resolution working on -DNFs instead of clauses -- for families of contradictions given in the {\em un…
cs.IT2016
Simplicial Complex Entropy
Stefan Dantchev, Ioannis Ivrissimtzis
We propose an entropy function for simplicial complices. Its value gives the expected cost of the optimal encoding of sequences of vertices of the complex, when any two vertices be…