דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
דין דורון (אונ' סטנפורד)
event date icon
יום רביעי, 18.12.2019, 12:30
event location icon
טאוב 201
Existing proofs that deduce P=BPP from circuit lower bounds convert randomized algorithms to deterministic ones with a large polynomial slowdown in running time. In this talk, I will show that if we assume exponential lower bounds against nondeterministic circuits, we can convert any randomized algorithm running in time T to a deterministic one running in time T^{2+����} for an arbitrarily small constant ����. Under complexity-theoretic assumptions, such a slowdown is nearly optimal.

Our result follows from a new pseudorandom generator whose construction uses, among other ideas, a new connection between pseudoentropy generators and locally list-recoverable codes.

Joint work with Dana Moshkovitz, Justin Oh and David Zuckerman