SU\G(𝔸)/K·U

Sherali-Adams and the binary encoding of combinatorial principles

Stefan Dantchev, Abdul Ghani, Barnaby Martin

Type: Preprint

Publication Date: 2019-11-01

Citations: 0

Locations

  • arXiv (Cornell University) - View

Similar Works

Action Title Year Authors
+ Sherali-Adams and the binary encoding of combinatorial principles 2019 Stefan Dantchev
Abdul Ghani
Barnaby Martin
+ Proof complexity and the binary encoding of combinatorial principles 2020 Stefan Dantchev
Nicola Galesi
Abdul Ghani
Barnaby Martin
+ PDF Chat Proof Complexity and the Binary Encoding of Combinatorial Principles 2024 Stefan Dantchev
Nicola Galesi
Abdul Ghani
Barnaby Martin
+ Resolution and the binary encoding of combinatorial principles 2018 Stefan Dantchev
Nicola Galesi
Barnaby Martin
+ Defying God: the Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics 2015 Eric S. Egge
+ Linear and Negative Resolution are weaker than Resolution 2001 J. Buresh-Oppenheim
David G. M. Mitchell
Toniann Pitassi
+ Refutation of Brouwer’s Dense Linear Orderings (Dlo) 2019 Colin James
+ Combinatorics and reasoning : representing, justifying and building isomorphisms 2011 Carolyn A. Maher
Arthur B. Powell
Elizabeth B. Uptegrove
+ Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. 2020 Fedor Part
Iddo Tzameret
+ Generating Pythagorean Triples, Patterns, and Magic Squares 2019 Inder J. Taneja
+ The Method of Proofs and Refutations 2001
+ The Method of Proofs and Refutations 2001
+ Resolution with Counting: Lower Bounds for Proofs of Membership in the Complement of a Linear Map Image of the Boolean Cube 2022 Fedor Part
+ 2 The Method of Proofs and Refutations 2020
+ Shortest Refutations of the Zermelo-Fraenkel (ZF) Axioms 2018 Colin James
+ Investigating Combinatorial Provers’ Reasoning about Multiplication 2020 Sarah A. Erickson
Elise Lockwood
+ Refutation of the Aafrempong Conjecture 2019 Colin James
+ Towards the shortest DRAT proof of the Pigeonhole Principle 2022 Isaac Grosof
Naifeng Zhang
Marijn J. H. Heule
+ Shortest Refutation of Gödel's Completeness Theorem Copyright © 2018 by Colin James III All Rights Reserved. 2018 Colin James
+ Refutation of Pythagorean Triples 2019 Colin James

Works That Cite This (0)

Action Title Year Authors

Works Cited by This (10)

Action Title Year Authors
+ Rank Lower Bounds for the Sherali-Adams Operator 2007 Mark Rhodes
+ An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs 2001 Jean B. Lasserre
+ PDF Chat Complexity of Semi-algebraic Proofs 2002 Dima Grigoriev
Edward Hirsch
Dmitrii V. áą–asechnik
+ Tight rank lower bounds for the Sherali–Adams proof system 2009 Stefan Dantchev
Barnaby Martin
Mark Rhodes
+ A Framework for Space Complexity in Algebraic Proof Systems 2015 Ilario Bonacina
Nicola Galesi
+ A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming 2001 Monique Laurent
+ PDF Chat The complexity of proving that a graph is Ramsey 2016 Massimo Lauria
Pavel Pudlák
Vojtěch Rödl
Neil Thapen
+ PDF Chat Tight Size-Degree Bounds for Sums-of-Squares Proofs 2017 Massimo Lauria
Jakob Nordstr”öm
+ Resolution and the binary encoding of combinatorial principles 2018 Stefan Dantchev
Nicola Galesi
Barnaby Martin
+ Sum of squares bounds for the total ordering principle. 2018 Aaron Potechin