You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: Middlesex University » Outputs » Detail

Output details

11 - Computer Science and Informatics

Middlesex University

Return to search Previous output Next output

Output 162 of 212 in the submission

Article title

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Type

D - Journal article

DOI

10.1007/s00037-012-0049-1

Title of journal

computational complexity

Article number

Volume number

Issue number

First page of article

191

ISSN of journal

1420-8954

Year of publication

2012

URL

http://dl.acm.org/citation.cfm?doid=2071368.2071373

Number of additional authors

Additional information

<10> The paper presents a proof of a dichotomy theorem for the rank of propositional contradictions, uniformly generated from first-order sentences, in the Integer Linear Programming (ILP) systems of Lovasz-Schrijver and Sherali-Adams (SA) when these are used as refutation systems. Thus this kind of gap theorem had not been known for ILP systems and our paper is in fact the first to consider the well-known SA system as a refutation system. The conference version of this paper appeared at the very highly regarded STOC conference.

Interdisciplinary

Cross-referral requested

Research group

None

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract