- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Lifting in Proof Complexity
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Lifting in Proof Complexity Vinyals, Marc
Description
A growing number of results in proof complexity rely on so-called "lifting" techniques (also called hardness escalation"), which are inspired from communication complexity. In the context of proof complexity, the basic idea of lifting is simple: in order to prove lower bounds in a proof system that is complex", start with a formula F that is hard for a "simple" proof system, and make the formula F harder by replacing each variable in F with some inner function that is hard to represent in the "complex" system. Often, we are able to show that the best proof for the composed formula in the complex proof system is to simulate the proof in the simple system --- thus, this reduces the lower bound problem from the complex proof system to proving lower bounds in the simple system, which is often much easier. In this survey talk, we will give an introduction to these techniques, survey some of the applications, and delineate when the techniques can be applied. No prior background in lifting techniques or communication complexity will be necessary.
Item Metadata
Title |
Lifting in Proof Complexity
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2020-01-22T09:02
|
Description |
A growing number of results in proof complexity rely on so-called "lifting" techniques (also called
hardness escalation"), which are inspired from communication complexity. In the context of proof
complexity, the basic idea of lifting is simple: in order to prove lower bounds in a proof system that is
complex", start with a formula F that is hard for a "simple" proof system, and make the formula F harder
by replacing each variable in F with some inner function that is hard to represent in the "complex" system.
Often, we are able to show that the best proof for the composed formula in the complex proof system is to simulate
the proof in the simple system --- thus, this reduces the lower bound problem from the complex proof system to proving
lower bounds in the simple system, which is often much easier.
In this survey talk, we will give an introduction to these techniques, survey some of the applications, and
delineate when the techniques can be applied. No prior background in lifting techniques or communication complexity
will be necessary.
|
Extent |
52.0 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Technion
|
Series | |
Date Available |
2020-07-21
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0392478
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International