All reports by Author Rohit Gurjar:

__
TR17-127
| 12th August 2017
__

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi#### Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

__
TR17-122
| 28th July 2017
__

Rohit Gurjar, Ben Lee Volk#### Pseudorandom Bits for Oblivious Branching Programs

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.

More precisely,

the property that we need is that every face of the polytope lies in an affine space defined ...
more >>>

Rohit Gurjar, Ben Lee Volk

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>