1 – 71 of 71
- show: 250
- |
- sort: year (new to old)
Close
Embed this list
<iframe src=" "
width=" "
height=" "
allowtransparency="true"
frameborder="0">
</iframe>
- 2024
-
Mark
KRW Composition Theorems via Lifting
(
- Contribution to journal › Article
-
Mark
End-to-End Verification for Subgraph Solving
2024) 38th AAAI Conference on Artificial Intelligence, AAAI 2024 In Proceedings of the AAAI Conference on Artificial Intelligence 38. p.8038-8047(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Proof Logging for the Circuit Constraint
2024) 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2024 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14743 LNCS. p.38-55(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certifying MIP-Based Presolve Reductions for 0–1 Integer Linear Programs
2024) 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2024 In Lecture Notes in Computer Science 14742. p.310-328(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certified MaxSAT Preprocessing
2024) 12th International Joint Conference, IJCAR 2024 In Lecture Notes in Computer Science 14739. p.396-418(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certifying Without Loss of Generality Reasoning in Solution-Improving Maximum Satisfiability
2024) 30th International Conference on Principles and Practice of Constraint Programming, CP 2024 In Leibniz International Proceedings in Informatics (LIPIcs) 307.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms
2024) 30th International Conference on Principles and Practice of Constraint Programming, CP 2024 In Leibniz International Proceedings in Informatics (LIPIcs) 307.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2023
-
Mark
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
(
- Contribution to journal › Article
-
Mark
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
2023) 29th International Conference on Principles and Practice of Constraint Programming, CP 2023(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certified Core-Guided MaxSAT Solving
2023) Proceedings of the 29th International Conference on Automated Deduction, CADE-29 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14132 LNAI. p.1-22(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certified Dominance and Symmetry Breaking for Combinatorial Optimisation
(
- Contribution to journal › Article
-
Mark
Certified CNF Translations for Pseudo-Boolean Solving (Extended Abstract)
(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
2023) 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS p.1-11(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2022
-
Mark
Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification
2022) 2022 Design, Automation and Test in Europe Conference and Exhibition, DATE 2022 In Proceedings of the 2022 Design, Automation and Test in Europe Conference and Exhibition, DATE 2022 p.1431-1436(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
An Auditable Constraint Programming Solver
2022) 28th International Conference on Principles and Practice of Constraint Programming, CP 2022 In Leibniz International Proceedings in Informatics, LIPIcs 235.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certified CNF Translations for Pseudo-Boolean Solving
2022) 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) In Leibniz International Proceedings in Informatics (LIPIcs) 236.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2021
-
Mark
Learn to relax : Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven search
(
- Contribution to journal › Article
-
Mark
Automating algebraic proof systems is NP-hard
2021) 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 In Proceedings of the Annual ACM Symposium on Theory of Computing p.209-222(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
(
- Contribution to journal › Article
-
Mark
Clique Is Hard on Average for Regular Resolution
(
- Contribution to journal › Article
-
Mark
The power of negative reasoning
2021) 36th Computational Complexity Conference, CCC 2021 In Leibniz International Proceedings in Informatics, LIPIcs 200.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Proof complexity and SAT solving
2021) p.233-350(
- Chapter in Book/Report/Conference proceeding › Book chapter
- 2020
-
Mark
Using Resolution Proofs to Analyse CDCL Solvers
2020) 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 In Lecture Notes in Computer Science 12333. p.427-444(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models
2020) 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 In Lecture Notes in Computer Science 12333. p.917-934(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems
2020) 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 In Lecture Notes in Computer Science 12333. p.338-357(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
2020) 35th Computational Complexity Conference, CCC 2020 In Leibniz International Proceedings in Informatics, LIPIcs 169.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Simplified and Improved Separations Between Regular and General Resolution by Lifting
2020) 23rd International Conference on Theory and Applications of Satisfiability Testing, SAT 2020 In Lecture Notes in Computer Science 12178. p.182-200(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Supercritical space-width trade-offs for resolution
(
- Contribution to journal › Article
-
Mark
Trade-offs between size and degree in polynomial calculus
2020) 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 In Leibniz International Proceedings in Informatics, LIPIcs 151.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
2020) 20th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2020 In Proceedings of the 20th Conference on Formal Methods in Computer-Aided Design, FMCAD 2020 p.194-204(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Lifting with simple gadgets and applications to circuit and proof complexity
2020) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2020-November. p.24-30(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
KRW composition theorems via lifting
2020) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2020-November. p.43-49(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2019
-
Mark
On division versus saturation in pseudo-boolean solving
2019) 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 In IJCAI International Joint Conference on Artificial Intelligence 2019-August. p.1711-1718(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Nullstellensatz size-degree trade-offs from reversible pebbling
2019) 34th Computational Complexity Conference, CCC 2019 In Leibniz International Proceedings in Informatics, LIPIcs 137.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2018
-
Mark
Seeking practical CDCL insights from theoretical SAT benchmarks
2018) 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 In IJCAI International Joint Conference on Artificial Intelligence 2018-July. p.1300-1308(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Divide and conquer : Towards faster pseudo-boolean solving
2018) 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 In IJCAI International Joint Conference on Artificial Intelligence 2018-July. p.1291-1299(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
In between resolution and cutting planes : A study of proof systems for pseudo-boolean SAT solving
2018) 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018 In Lecture Notes in Computer Science 10929. p.292-310(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers
2018) 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018 In Lecture Notes in Computer Science 10929. p.75-93(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Clique is hard on average for regular resolution
2018) 50th Annual ACM Symposium on Theory of Computing, STOC 2018 In Proceedings of the Annual ACM Symposium on Theory of Computing p.646-659(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2017
-
Mark
Cumulative space in black-white pebbling and resolution
2017) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 In Leibniz International Proceedings in Informatics, LIPIcs 67.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
2017) 32nd Computational Complexity Conference, CCC 2017 In Leibniz International Proceedings in Informatics, LIPIcs 79.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
CNFgen : A generator of crafted benchmarks
2017) 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017 In Lecture Notes in Computer Science 10491. p.464-473(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Tight Size-Degree Bounds for Sums-of-Squares Proofs
(
- Contribution to journal › Article
- 2016
-
Mark
Supercritical space-width trade-offs for resolution
2016) 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 In Leibniz International Proceedings in Informatics, LIPIcs 55.(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)
2016) 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016-December. p.295-304(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps
2016) 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 In Proceedings - Symposium on Logic in Computer Science 05-08-July-2016. p.267-276(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Trade-offs between time and memory in a tighter model of CDCL SAT solvers
2016) 19th International Conference on Theory and Applications of Satisfiability Testing, SAT 2016 In Lecture Notes in Computer Science 9710. p.160-176(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Narrow proofs may be maximally long
(
- Contribution to journal › Article
- 2015
-
Mark
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
2015) 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015-December. p.466-485(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
A generalized method for proving polynomial calculus degree lower bounds
2015) 30th Conference on Computational Complexity, CCC 2015 In Leibniz International Proceedings in Informatics, LIPIcs 33. p.467-487(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Tight size-degree bounds for sums-of-squares proofs
2015) 30th Conference on Computational Complexity, CCC 2015 In Leibniz International Proceedings in Informatics, LIPIcs 33. p.448-466(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
From small space to small width in resolution
(
- Contribution to journal › Article
-
Mark
Space complexity in polynomial calculus
(
- Contribution to journal › Article
- 2014
-
Mark
Long Proofs of (Seemingly) Simple Formulas
2014) 17th International Conference on Theory and Applications of Satisfiability Testing, SAT 2014, Held as Part of the Vienna Summer of Logic, VSL 2014 In Lecture Notes in Computer Science 8561. p.121-137(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
A (biased) proof complexity survey for SAT practitioners
2014) 17th International Conference on Theory and Applications of Satisfiability Testing, SAT 2014, Held as Part of the Vienna Summer of Logic, VSL 2014 In Lecture Notes in Computer Science 8561. p.1-6(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
From small space to small width in resolution
2014) 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 In Leibniz International Proceedings in Informatics, LIPIcs 25. p.300-311(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Narrow proofs may be maximally long
2014) 29th Annual IEEE Conference on Computational Complexity, CCC 2014 In Proceedings of the Annual IEEE Conference on Computational Complexity p.286-297(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2013
-
Mark
Towards an understanding of polynomial calculus : New separations and lower bounds (extended abstract)
2013) 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 In Lecture Notes in Computer Science 7965(PART 1). p.437-448(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Some trade-off results for polynomial calculus
2013) 45th Annual ACM Symposium on Theory of Computing, STOC 2013 In Proceedings of the Annual ACM Symposium on Theory of Computing p.813-822(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Pebble games, proof complexity, and time-space trade-offs
(
- Contribution to journal › Article
- 2012
-
Mark
Relating proof complexity measures and practical hardness of SAT
2012) 18th International Conference on Principles and Practice of Constraint Programming, CP 2012 In Lecture Notes in Computer Science 7514. p.316-331(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Space complexity in polynomial calculus
2012) IEEE Computer Society Technical Committee on Mathematical Foundations of Computing In Proceedings of the Annual IEEE Conference on Computational Complexity p.334-344(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
On the virtue of succinct proofs : Amplifying communication complexity hardness to time-space trade-offs in proof complexity
2012) 44th Annual ACM Symposium on Theory of Computing, STOC '12 In Proceedings of the Annual ACM Symposium on Theory of Computing p.233-247(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
On the relative strength of pebbling and resolution
(
- Contribution to journal › Article
- 2011
-
Mark
On minimal unsatisfiability and time-space trade-offs for k-DNF resolution
2011) 38th International Colloquium on Automata, Languages and Programming, ICALP 2011 In Lecture Notes in Computer Science 6755(PART 1). p.642-653(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2010
-
Mark
On the relative strength of pebbling and resolution
2010) 25th Annual IEEE Conference on Computational Complexity, CCC 2010 In Proceedings of the Annual IEEE Conference on Computational Complexity p.151-162(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2009
-
Mark
A simplified way of proving trade-off results for resolution
(
- Contribution to journal › Article
-
Mark
Narrow proofs may be spacious : Separating space and width in resolution
(
- Contribution to journal › Article
- 2008
-
Mark
Short proofs may be spacious : An optimal separation of space and length in resolution
2008) 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS p.709-718(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
-
Mark
Towards an optimal separation of space and length in resolution
2008) 40th Annual ACM Symposium on Theory of Computing, STOC 2008 In Proceedings of the Annual ACM Symposium on Theory of Computing p.701-710(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
- 2006
-
Mark
Narrow proofs may be spacious : Separating space and width in resolution
2006) 38th Annual ACM Symposium on Theory of Computing, STOC'06 In Proceedings of the Annual ACM Symposium on Theory of Computing 2006. p.507-516(
- Chapter in Book/Report/Conference proceeding › Paper in conference proceeding