dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

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

  • Start Date: March 28, 2018
  • Event Start Time: 11:00 AM
  • Event End Time: 12:00 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Sumegha Garg - Princeton University
  • Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    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 the optimal O(log(n) + log(1/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL, respectively.