Department Seminars & Colloquia

Category 학과 Seminar/ Colloquium
Event Discrete Math
Title Space Proof Complexity for Random 3-CNFs
Abstract
During the last decade, an active line of research in proof complexity has been the space complexity of proofs and how space is related to other complexity measures (like size, length, width, degree). Space is (roughly) how large of an erasable board one would need to show a proof line-by-line.
 
Here, we are interested in the space complexity of refuting 3-CNFs (formulas in conjunctive normal form with at most 3 literals per clause). We prove that a random 3-CNF with n variables requires, with high probability, Ω(n2) total space in Resolution. This is best possible up to a constant factor.
 
This lower bound is obtained via a variant of Hall’s Lemma which may be of independent interest. Namely, we show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2-ε), for ε < 1/23.
This is joint work with Patrick Bennett, Ilario Bonacina, Nicola Galesi, Mike Molloy, and Paul Wollan.
Daytime 2015-06-02 (Tue) / 16:00 ~ 17:00 ** 날짜에 유의하세요. **
Place 자연과학동 E6-1, ROOM 1409
Language English
Speaker`s name Tony Huynh
Speakers`s Affiliation Sapienza Università di Roma
Speaker`s homepage
Other information
Hosts 엄상일
URL http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20150602/
담당자
연락처