Bounded-depth Frege complexity of Tseitin formulas for all graphs. (English) Zbl 1516.03021
Reviewer: Ariel Germán Fernández (Buenos Aires)
Found 16 Documents (Results 1–16)
Tight bounds for tseitin formulas. (English) Zbl 07880727
Meel, Kuldeep S. (ed.) et al., 25th international conference on theory and applications of satisfiability testing, SAT 2022, Haifa, Israel, August 2–5, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 236, Article 6, 21 p. (2022).
On the complexity of branching proofs. (English) Zbl 07561762
Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 34, 35 p. (2020).
MSC:
68Q25
Reordering rule makes OBDD proof systems stronger. (English) Zbl 1441.03042
Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 16, 24 p. (2018).
On OBDD-based algorithms and proof systems that dynamically change order of variables. (English) Zbl 1402.68097
Vollmer, Heribert (ed.) et al., 34th symposium on theoretical aspects of computer science (STACS 2017), Hannover, Germany, March 8–11, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-028-6). LIPIcs – Leibniz International Proceedings in Informatics 66, Article 43, 14 p. (2017).
Some trade-off results for polynomial calculus (extended abstract). (English) Zbl 1293.03031
Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 813-822 (2013).
Boolean function complexity. Advances and frontiers. (English) Zbl 1235.94005
Algorithms and Combinatorics 27. Berlin: Springer (ISBN 978-3-642-24507-7/hbk; 978-3-642-24508-4/ebook). xv, 617 p. (2012).
Reviewer: Ioan Tomescu (Bucureşti)
The strength of multilinear proofs. (English) Zbl 1174.03025
Reviewer: Emil Jeřábek (Praha)
Lower bounds for space in resolution. (English) Zbl 0942.03010
Flum, Jörg (ed.) et al., Computer science logic. 13th international workshop, CSL ’99. 8th annual conference of the EACSL, Madrid, Spain, September 20-25, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1683, 362-373 (1999).
Automated deduction and integer programming. (English) Zbl 0838.03010
Collegium Logicum. Annals of the Kurt-Gödel-Society. Vol. 1. Wien: Springer-Verlag. 67-86 (1995).
Tseitin’s formulas revisited. (English) Zbl 0754.05065
Filter Results by …
Document Type
- Journal Articles (8)
- Collection Articles (7)
- Books (1)
all
top 5
Author
- Itsykson, Dmitry M. (6)
- Knop, Alexander (3)
- Riazanov, Artur (3)
- Sokolev, Dmitry (3)
- Buss, Samuel R. (2)
- Tzameret, Iddo (2)
- Beck, Chris (1)
- Chubaryan, Anahit A. (1)
- Dadush, Daniel (1)
- Dzhugaryan, A. G. (1)
- Fouks, Jean-Denis (1)
- Galesi, Nicola (1)
- Glinskih, Ludmila (1)
- Hähnle, Reiner (1)
- Koucký, Michal (1)
- Nordström, Jakob (1)
- Part, Fedor (1)
- Raz, Ran (1)
- Rodl, Vojtech (1)
- Romashchenko, Andrei (1)
- Smirnov, Petr (1)
- Sofronova, Anastasia (1)
- Talebanfard, Navid (1)
- Tang, Bangsheng (1)
- Tiwari, Samarth (1)
- Torán, Jacobo (1)
- Yukna, Stasys P. (1)
- Zoryan, G. N. (1)
Software
- PolyBoRi (1)
