Found 19 Documents (Results 1–19)
Propositional proof complexity. (English) Zbl 1541.03155
Hujdurović, Ademir (ed.) et al., European congress of mathematics. Proceedings of the 8th congress, 8ECM, Portorož, Slovenia, June 20–26, 2021. Berlin: European Mathematical Society (EMS). 439-464 (2023).
Reviewer: Ariel Germán Fernández (Buenos Aires)
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. (English) Zbl 07561756
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 28, 24 p. (2020).
MSC:
68Q25
Resolution and the binary encoding of combinatorial principles. (English) Zbl 07564406
Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 6, 25 p. (2019).
MSC:
68Q25
Improved algorithms for optimal length resolution refutation in difference constraint systems. (English) Zbl 1259.68261
Optimal length resolution refutations of difference constraint systems. (English) Zbl 1184.68468
MSC:
68T15
Resolution over linear equations and multilinear proofs. (English) Zbl 1161.03034
Reviewer: Emil Jeřábek (Praha)
MSC:
03F20
Width versus size in resolution proofs. (English) Zbl 1124.03031
MSC:
03F20
Resolution lower bounds for the weak functional pigeonhole principle. (English) Zbl 1050.03039
Reviewer: Nail Zamov (Kazan)
Lower bounds for the weak pigeonhole principle and random formulas beyond resolution. (English) Zbl 1012.03058
A new proof of the weak pigeonhole principle. (English) Zbl 1051.03049
MSC:
03F20
Space bounds for resolution. (English) Zbl 1005.03009
A new proof of the weak pigeonhole principle. (English) Zbl 1296.03033
Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 368-377 (2000).
MSC:
03F20
Short proofs are narrow – resolution made simple. (English) Zbl 1346.68173
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 517-526 (1999).
Filter Results by …
Document Type
- Journal Articles (14)
- Collection Articles (5)
all
top 5
Author
- Dantchev, Stefan Stoyanov (3)
- Martin, Barnaby D. (3)
- Razborov, Aleksandr Aleksandrovich (3)
- Esteban, Juan Luis (2)
- Galesi, Nicola (2)
- Maciel, Alexis (2)
- Nordström, Jakob (2)
- Pitassi, Toniann (2)
- Subramani, Krishnan (2)
- Woods, Alan Robert (2)
- Atserias, Albert (1)
- Ben-Sasson, Eli (1)
- Bonet, Maria Luisa (1)
- de Rezende, Susanna F. (1)
- Filmus, Yuval (1)
- Gu, Xiaofeng (1)
- Lauria, Massimo (1)
- Raz, Ran (1)
- Risse, Kilian (1)
- Seto, Kazuhisa (1)
- Szeider, Stefan (1)
- Thapen, Neil (1)
- Torán, Jacobo (1)
- Tzameret, Iddo (1)
- Urquhart, Alasdair (1)
- Wigderson, Avi (1)
- Williamson, Matthew (1)
all
top 5
Serial
- J. Comput. Syst. Sci. (2)
- SIAM J. Comput. (2)
- Theor. Comput. Sci. (2)
- Inf. Comput. (2)
- Ann. Pure Appl. Logic (1)
- J. Autom. Reasoning (1)
- Formal Asp. Comput. (1)
- Comput. Complexity (1)
- Theory Comput. Syst. (1)
- Interdiscip. Inf. Sci. (1)
