Irit Dinur: Lifting locally consistent partial solutions to a global solution

Practicalities

Lunch is served at 12:00 noon (register at this doodle at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

We are given a collection of (alleged) partial views of a function. We are promised "local consistency", i.e., that the partial views agree on their intersection with probability p. The question is whether the partial views can be lifted to a global function f, i.e. whether a p' fraction of the partial views agree with f (aka "global consistency").

This scenario captures "low degree tests" and "direct product tests", both studied for constructions of PCPs. We describe other possible settings where a lifting theorem may hold. We will relate this to questions on proving a "derandomized" parallel repetition theorem, and the sliding scale conjecture.