D. Sivakumar

STOC Conference 2002 Conference Paper

Algorithmic derandomization via complexity theory

• D. Sivakumar

We point out how the methods of Nisan [31, 32], originally developed for derandomizing space-bounded computations, may be applied to obtain polynomial-time and NC derandomizations of several probabilistic algorithms. Our list includes the randomized rounding steps of linear and semi-definite programming relaxations of optimization problems, parallel derandomization of discrepancy-type problems, and the Johnson--Lindenstrauss lemma, to name a few.A fascinating aspect of this style of derandomization is the fact that we often carry out the derandomizations directly from the statements about the correctness of probabilistic algorithms, rather than carefully mimicking their proofs.

TCS Journal 2001 Journal Article

On the unique shortest lattice vector problem

• S. Ravi Kumar
• D. Sivakumar

We show that the problem of deciding whether a given rational lattice L has a vector of length less than some given value r is NP-hard, even under the promise that L has exactly zero or one vector of length less than r.

TCS Journal 2000 Journal Article

Resolution of Hartmanis’ conjecture for NL-hard sparse sets

• Jin-Yi Cai
• D. Sivakumar

We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for nondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL=L (deterministic logspace).

STOC Conference 1999 Conference Paper

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time

• Jin-Yi Cai
• Ajay Nerurkar
• D. Sivakumar

FOCS Conference 1997 Conference Paper

Constant Depth Circuits and the Lutz Hypothesis

• Jin-Yi Cai
• D. Sivakumar
• Martin J. Strauss

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

TCS Journal 1995 Journal Article

On quasilinear-time complexity theory

• Ashish V. Naik
• Kenneth W. Regan
• D. Sivakumar

This paper furthers the study of quasilinear-time complexity initiated by Schnorr and Gurevich and Shelah. We show that the fundamental properties of the polynomial-time hierarchy carry over to the quasilinear-time hierarchy. Whereas all previously known versions of the Valiant-Vazirani reduction from NP to parity run in quadratic time, we give a new construction using error-correcting codes that runs in quasilinear time. We show, however, that the important equivalence between search problems and decision problems in polynomial time is unlikely to carry over: if search reduces to decision for SAT in quasilinear time, then all of NP is contained in quasipolynomial time. Other connections are made to work by Stearns and Hunt on “power indices” of NP languages, and to work on bounded-query Turing reductions and helping by robust oracle machines.

FOCS Conference 1995 Conference Paper

Pseudorandom Generators, Measure Theory, and Natural Proofs

• Kenneth W. Regan
• D. Sivakumar
• Jin-Yi Cai

We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.

FOCS Conference 1995 Conference Paper

The Resolution of a Hartmanis Conjecture

• Jin-Yi Cai
• D. Sivakumar

Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC/sup 1/, then P collapses to NC/sup 1/.