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/ |
담당자 | |
연락처 |