All reports by Author A. Pavan:

__
TR21-043
| 15th March 2021
__

Peter Dixon, A. Pavan, N. V. Vinodchandran#### Promise Problems Meet Pseudodeterminism

__
TR19-091
| 7th July 2019
__

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

__
TR14-126
| 9th October 2014
__

Debasis Mandal, A. Pavan, Rajeswari Venugopalan#### Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis

__
TR14-035
| 13th March 2014
__

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang#### New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

__
TR10-009
| 13th January 2010
__

A. Pavan, Raghunath Tewari, N. V. Vinodchandran#### On the Power of Unambiguity in Logspace

__
TR09-071
| 1st September 2009
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Kolmogorov Complexity in Randomness Extraction

__
TR06-071
| 25th April 2006
__

John Hitchcock, A. Pavan#### Hardness Hypotheses, Derandomization, and Circuit Complexity

__
TR06-039
| 28th February 2006
__

John Hitchcock, A. Pavan#### Comparing Reductions to NP-Complete Sets

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR05-068
| 7th July 2005
__

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang#### Redundancy in Complete Sets

__
TR05-062
| 17th June 2005
__

A. Pavan, N. V. Vinodchandran#### 2-Local Random Reductions to 3-Valued Functions

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR04-053
| 17th June 2004
__

A. Pavan, N. V. Vinodchandran#### Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

__
TR04-025
| 24th January 2004
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Partial Bi-Immunity and NP-Completeness

__
TR04-019
| 15th January 2004
__

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta#### Properties of NP-Complete Sets

__
TR02-005
| 3rd January 2002
__

A. Pavan, Alan L. Selman#### Bi-Immunity Separates Strong NP-Completeness Notions

__
TR01-032
| 3rd April 2001
__

A. Pavan, Alan L. Selman#### Separation of NP-completeness Notions

Peter Dixon, A. Pavan, N. V. Vinodchandran

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

Debasis Mandal, A. Pavan, Rajeswari Venugopalan

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.

(1) A polynomial-time,

$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ...
more >>>

A. Pavan, Raghunath Tewari, N. V. Vinodchandran

We report progress on the \NL\ vs \UL\ problem.

\begin{itemize}

\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.

\item[-] We investigate the complexity of min-uniqueness - a central

notion in studying the \NL\ vs \UL\ problem.

more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity

extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction

more >>>

John Hitchcock, A. Pavan

We consider hypotheses about nondeterministic computation that

have been studied in different contexts and shown to have interesting

consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be

distinguished from any DTIME(2^n^epsilon) language by an ...
more >>>

John Hitchcock, A. Pavan

Under the assumption that NP does not have p-measure 0, we

investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive

reductions: there is a problem that is Turing-complete for NP but

not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

A. Pavan, N. V. Vinodchandran

Yao (in a lecture at DIMACS Workshop on structural complexity and

cryptography) showed that if a language L is 2-locally-random

reducible to a Boolean functio, then L is in PSPACE/poly.

Fortnow and Szegedy quantitatively improved Yao's result to show that

such languages are in fact in NP/poly (Information Processing Letters, ...
more >>>

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>A. Pavan, N. V. Vinodchandran

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine

and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

John Hitchcock, A. Pavan, N. V. Vinodchandran

The Turing and many-one completeness notions for $\NP$ have been

previously separated under {\em measure}, {\em genericity}, and {\em

bi-immunity} hypotheses on NP. The proofs of all these results rely

on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such ...
more >>>

A. Pavan, Alan L. Selman

We prove that if for some epsilon > 0 NP contains a set that is

DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing

complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo

(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the

same consequence using strong ...
more >>>

A. Pavan, Alan L. Selman

We use hypotheses of structural complexity theory to separate various

NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ...
more >>>