Tight rank lower bounds for the Sherali–Adams proof system

Article

Dantchev, S., Martin, B. and Rhodes, M. 2009. Tight rank lower bounds for the Sherali–Adams proof system. Theoretical Computer Science. 410 (21-23), pp. 2054-2063. https://doi.org/10.1016/j.tcs.2009.01.002
TypeArticle
TitleTight rank lower bounds for the Sherali–Adams proof system
AuthorsDantchev, S., Martin, B. and Rhodes, M.
Abstract

We consider a proof (more accurately, refutation) system based on the Sherali-Adams (SA) operator associated with integer linear programming.

Research GroupFoundations of Computing group
PublisherElsevier Science
JournalTheoretical Computer Science
ISSN0304-3975
Publication dates
PrintMay 2009
Publication process dates
Deposited20 Dec 2012
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1016/j.tcs.2009.01.002
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/83wy4

Log in to edit
  • 15
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as