5 papers
Proceedings Tenth Symposium on Working Formal Methods
Mircea Marin, Adrian Crăciun
The 10th Working Formal Methods Symposium (FROM 2026) was held in Timişoara, Romania on September 15-17, 2026. It was organized jointly by the Faculty of Informatics of West Univer…
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…
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…
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…
Proof Complexity and the Kneser-Lovász Theorem
Gabriel Istrate, Adrian Crăciun
We investigate the proof complexity of a class of propositional formulas expressing a combinatorial principle known as the Kneser-Lovász Theorem. This is a family of propositional…