Now showing items 1-1 of 1

    • Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs 

      Steinke, Thomas Alexander; Vadhan, Salil P.; Wan, Andrew (Dagstuhl Publishing, 2014)
      We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed ...