CS Events

Qualifying Exam

Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL.

 

Download as iCal file

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