3 papers
cs.CC2021
Kernelization, Proof Complexity and Social Choice
Gabriel Istrate, Cosmin Bonchis, Adrian Craciun
We display an application of the notions of kernelization and data reduction from parameterized complexity to proof complexity: Specifically, we show that the existence of data red…
cs.SC2019
Gröbner Bases with Reduction Machines
Georgiana Şurlea, Adrian Crăciun
In this paper, we make a contribution to the computation of Gröbner bases. For polynomial reduction, instead of choosing the leading monomial of a polynomial as the monomial with r…
math.LO2015
Short Proofs of the Kneser-Lovász Coloring Principle
James Aisenberg, Maria Luisa Bonet, Sam Buss +2
We prove that the propositional translations of the Kneser-Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counti…