CS Events
Qualifying ExamLower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL. |
|
||
Tuesday, November 05, 2024, 02:20pm - 03:20pm |
|||
Speaker: Songhua He
Location : CoRE 431
Committee:
Professor Jie Gao
Professor Sumegha Garg
Professor Roie Levin
Professor Periklis A. Papakonstantinou
Professor Michael E. Saks
Event Type: Qualifying Exam
Abstract: We study a novel information-theoretic query model, the query-with-sketch model, and its lower bounds. As an application, we obtain a barrier in derandomizing BPL.The query-with-sketch model extends the traditional query model by incorporating an agent that provides the algorithm with a short sketch of the input. The trade-off between the length of the sketch and the query complexity of the algorithm becomes interesting. Specifically, we establish a lower bound in this model for the Approximate Matrix Powering (AMP) problem, showing that, in a recursive generalization of the query-with-sketch model, AMP requires either polynomial query complexity or superpolynomial sketch length.Derandomizing BPL has long been a central question in complexity theory. Building on foundational results from [Nis92] and [SZ99], significant efforts have aimed to prove BPL = L. Currently, the best-known derandomization approach places BPL within SPACE(\log^{3/2}n/\sqrt{\log\log n}). Our lower bound above implies that, fully derandomizing BPL cannot rely on a natural, recursive use of approximated intermediate powers.
:
Contact Professor Jie Gao
List of publications:
The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks.
with Periklis A. Papakonstantinou
ICML 2024
Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL.
with Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang