Skip navigation
Please use this identifier to cite or link to this item:
Title: Query-To-Communication Lifting Theorems
Authors: Intrater, Jake
Advisors: Yu, Huacheng
Department: Mathematics
Class Year: 2023
Abstract: Given a two-party gadget function g : X × Y → {0, 1} and an outer lifting function f : {0, 1} n → {0, 1}, we can define F = f◦g n : X n×Yn → {0, 1} that treats the input (x, y) = ((x1, . . . , xn),(y1, . . . , yn)) as n ‘blocks’and outputs F(x, y) = f(g(x1, y1),(x2, y2), . . . ,(xn, yn)). Using theorems of G¨o¨os, Kamath, Pitassi and Watson, I set out to explore the conditions on f, g and n, in various computational settings, that make it possible to decompose the complexity of F in terms of the complexity of f and g. These results lead directly to various bounds and counter-examples all across the complexity zoo.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2023

Files in This Item:
File Description SizeFormat 
INTRATER-JAKE-THESIS.pdf487.94 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.