Subhas Kumar Ghosh

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>

Vikraman Arvind, Partha Mukhopadhyay

We give a randomized polynomial-time identity test for

noncommutative circuits of polynomial degree based on the isolation

lemma. Using this result, we show that derandomizing the isolation

lemma implies noncommutative circuit size lower bounds. More

precisely, we consider two restricted versions of the isolation

lemma and show that derandomizing each ...
more >>>

Valentine Kabanets, Osamu Watanabe

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>

Noam Ta-Shma

We give a new simple proof for the Isolation Lemma, with slightly better parameters, that also gives non-trivial results even when the weight domain $m$ is smaller than the number of variables $n$.

more >>>Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Shafi Goldwasser, Ofer Grossman

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

Vaibhav Krishan, Nutan Limaye

In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>>

Rohit Gurjar, Thomas Thierauf

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

Dieter van Melkebeek, Gautam Prakriya

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

Ola Svensson, Jakub Tarnawski

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

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 >>>

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices

$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous

logarithmic space.