CS Events Monthly View

Seminar

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

 

Download as iCal file

Wednesday, March 28, 2018, 11:00am
 

Nisan [Nis92] constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error ε and seed length O(log^2(n) + log(n) · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to th

Speaker: Sumegha Garg

Bio

I am a third year PhD student in the Department of Computer Science at Princeton University. I am extremely fortunate to be advised by Mark Braverman. Before coming here, I finished my undergraduate studies in the Department of Computer Science and Engine

Location : CoRE 301

Committee: 

Pranjal Awasthi and Shubhangi Saraf

Event Type: Seminar

Abstract: 

Organization: 

Princeton University