Title	k-Clique and Regular vs. General Resolution
Creator	Pang, Shuo
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2020-01-23T11:30
Description	For the average hardness of $k$-clique CNF, we have the $2^k$-type lower bound for general resolution, and the ideal $n^k$-type for regular resolution. What's difficult in getting the ideal lbd for general resolution Is regularity really important here We examine known separations of general vs. regular, and show that they actually all separate a middle model (called ``a-irregular'') from regular. It also turns out, $k$-Clique goes past (ie., is hard for) this model. Thus the difficulty comes from, not surprisingly, those ``very irregular'' proofs.
Extent	22.0 minutes
Subject	Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Chicago
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2020-07-22
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0392492
URI	http://hdl.handle.net/2429/75240
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Graduate
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos