8 citations · 16 across the 15 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
Pseudorandom Bits for Oblivious Branching Programs
Rohit Gurjar, Ben Lee Volk
We construct a pseudorandom generator which fools read- oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequen…
cs.CC2017★ 1 cited
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bound…