Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Sökning: onr:"swepub:oai:DiVA.org:kth-249607" > Lifting with Simple...

1 av 1
Föregående post
Nästa post
Till träfflistan

de Rezende, Susanna F.,1989-KTH,Teoretisk datalogi, TCS (författare)

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

BokEngelska

Förlag, utgivningsår, omfång ...

printrdacarrier

Nummerbeteckningar

LIBRIS-ID:oai:DiVA.org:kth-249607
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-249607URI

Kompletterande språkuppgifter

Språk:engelska
Sammanfattning på:engelska

Ingår i deldatabas

SwePubSwePub

Klassifikation

Ämneskategori:vet swepub-contenttype
Ämneskategori:ovr swepub-publicationtype

Anmärkningar

QC 20190529
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems:We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomialline space if coefficients are restricted to be of polynomial magnitude.We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known.An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.

Ämnesord och genrebeteckningar

NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
Computer Science
Datalogi

Biuppslag (personer, institutioner, konferenser, titlar ...)

Meir, Or (författare)
Nordström, Jakob,1972-KTH,Teoretisk datalogi, TCS(Swepub:kth)u1mbi3f0 (författare)
Toniann, Pitassi (författare)
Robere, Robert (författare)
Vinyals, Marc (författare)
KTHTeoretisk datalogi, TCS (creator_code:org_t)

Internetlänk

https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-249607

Till lärosätets databas

1 av 1
Föregående post
Nästa post
Till träfflistan

Hitta mer i SwePub

Av författaren/redakt...: de Rezende, Susa ...; Meir, Or; Nordström, Jakob ...; Toniann, Pitassi; Robere, Robert; Vinyals, Marc

Om ämnet

NATURVETENSKAP: NATURVETENSKAP; och Data och informa ...; och Datavetenskap

Av lärosätet: Kungliga Tekniska Högskolan

Sök utanför SwePub

Sök vidare i:: Google; Google Book Search; Google Scholar

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

LIBRIS.kb.se