Source author record

Nitin Saurabh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Computational Geometry Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Tight Lower Bounds for Approximate & Exact $k$ -Center in $\mathbb{R}^d$

In the discrete $k$ -center problem, we are given a metric space $(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq P$ of $k$ centers which minimizes the maximum distance of a point in $P$ from its nearest center. For any $ε>0$ , Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an $(1+ε)$ -approximation algorithm for this problem in $d$ -dimensional Euclidean space which runs in $O(dn\log k) + \left(\dfrac{k}ε\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$ time. In this paper we show that their algorithm is essentially optimal: if for some $d\geq 2$ and some computable function $f$ , there is an $f(k)\cdot \left(\dfrac{1}ε\right)^{o\left(k^{1-1/d}\right)} \cdot n^{o\left(k^{1-1/d}\right)}$ time algorithm for $(1+ε)$ -approximating the discrete $k$ -center on $n$ points in $d$ -dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a $d$ -dimensional constraint satisfaction problem (CSP) defined by Marx and Sidiropoulos [SoCG '14] to discrete $d$ -dimensional $k$ -center. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in $n^{O\left(d\cdot k^{1-1/d}\right)}$ time for discrete $k$ -center on $n$ points in $d$ -dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some $d\geq 2$ and some computable function $f$ , there is an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time exact algorithm for the discrete $k$ -center problem on $n$ points in $d$ -dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for $d=2$ and was implicit in the work of Marx [IWPEC '06]. [see paper for full abstract]

preprint2020arXiv

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most $k$ is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.

preprint2020arXiv

On the complexity of detecting hazards

Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no $O(3^{(1-ε)n} \text{poly}(s))$ time algorithm, for any $ε> 0$ , that detects logic hazards in Boolean circuits of size $s$ on $n$ variables under the assumption that the strong exponential time hypothesis is true. This lower bound holds even when the input circuits are restricted to be formulas of depth four. We also present a polynomial time algorithm for detecting $1$ -hazards in DNF (or, $0$ -hazards in CNF) formulas. Since $0$ -hazards in DNF (or, $1$ -hazards in CNF) formulas are easy to eliminate, this algorithm can be used to detect whether a given DNF or CNF formula has a hazard in practice.

preprint2016arXiv

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

We provide a list of new natural $\mathsf{VNP}$ -intermediate polynomial families, based on basic (combinatorial) $\mathsf{NP}$ -complete problems that are complete under parsimonious reductions. Over finite fields, these families are in $\mathsf{VNP}$ , and under the plausible hypothesis $\mathsf{Mod}_p\mathsf{P} \not\subseteq \mathsf{P/poly}$ , are neither $\mathsf{VNP}$ -hard (even under oracle-circuit reductions) nor in $\mathsf{VP}$ . Prior to this, only the Cut Enumerator polynomial was known to be $\mathsf{VNP}$ -intermediate, as shown by Bürgisser in 2000. We next show that over rationals and reals, two of our intermediate polynomials, based on satisfiability and Hamiltonian cycle, are not monotone affine polynomial-size projections of the permanent. This augments recent results along this line due to Grochow. Finally, we describe a (somewhat natural) polynomial defined independent of a computation model, and show that it is $\mathsf{VP}$ -complete under polynomial-size projections. This complements a recent result of Durand et al. (2014) which established $\mathsf{VP}$ -completeness of a related polynomial but under constant-depth oracle circuit reductions. Both polynomials are based on graph homomorphisms. A simple restriction yields a family similarly complete for $\mathsf{VBP}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nitin Saurabh

Research overview

Is this your work?

4 publications

Tight Lower Bounds for Approximate & Exact $k$ -Center in $\mathbb{R}^d$

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

On the complexity of detecting hazards

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

See the researcher in context

Building this map preview

Nitin Saurabh

Research overview

Is this your work?

4 publications

Tight Lower Bounds for Approximate & Exact kkk-Center in Rd\mathbb{R}^dRd

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

On the complexity of detecting hazards

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

See the researcher in context

Building this map preview

Tight Lower Bounds for Approximate & Exact $k$ -Center in $\mathbb{R}^d$