Source author record

Amey Bhangale

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

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

A Characterization of hard-to-cover CSPs

We continue the study of the covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Comp. 2002] and Dinur and Kol [CCC'13]. The covering number of a CSP instance $Φ$ is the smallest number of assignments to the variables of $Φ$ , such that each constraint of $Φ$ is satisfied by at least one of the assignments. We show the following results: 1. Assuming a covering variant of the Unique Games Conjecture, introduced by Dinur and Kol, we show that for every non-odd predicate $P$ over any constant-size alphabet and every integer $K$ , it is NP-hard to approximate the covering number within a factor of $K$ . This yields a complete characterization of CSPs over constant-size alphabets that are hard to cover. 2. For a large class of predicates that are contained in the 2k-LIN predicate, we show that it is quasi-NP-hard to distinguish between instances with covering number at most $2$ and those with covering number at least $Ω(\log\log n)$ . This generalizes and improves the 4-LIN covering hardness result of Dinur and Kol.

preprint2020arXiv

Hardness of Approximation of (Multi-)LCS over Small Alphabet

The problem of finding longest common subsequence (LCS) is one of the fundamental problems in computer science, which finds application in fields such as computational biology, text processing, information retrieval, data compression etc. It is well known that (decision version of) the problem of finding the length of a LCS of an arbitrary number of input sequences (which we refer to as Multi-LCS problem) is NP-complete. Jiang and Li [SICOMP'95] showed that if Max-Clique is hard to approximate within a factor of $s$ then Multi-LCS is also hard to approximate within a factor of $Θ(s)$ . By the NP-hardness of the problem of approximating Max-Clique by Zuckerman [ToC'07], for any constant $δ>0$ , the length of a LCS of arbitrary number of input sequences of length $n$ each, cannot be approximated within an $n^{1-δ}$ -factor in polynomial time unless {\tt{P}} $=$ {\NP}. However, the reduction of Jiang and Li assumes the alphabet size to be $Ω(n)$ . So far no hardness result is known for the problem of approximating Multi-LCS over sub-linear sized alphabet. On the other hand, it is easy to get $1/|Σ|$ -factor approximation for strings of alphabet $Σ$ . In this paper, we make a significant progress towards proving hardness of approximation over small alphabet by showing a polynomial-time reduction from the well-studied \emph{densest $k$ -subgraph} problem with {\em perfect completeness} to approximating Multi-LCS over alphabet of size $poly(n/k)$ . As a consequence, from the known hardness result of densest $k$ -subgraph problem (e.g. [Manurangsi, STOC'17]) we get that no polynomial-time algorithm can give an $n^{-o(1)}$ -factor approximation of Multi-LCS over an alphabet of size $n^{o(1)}$ , unless the Exponential Time Hypothesis is false.

preprint2020arXiv

Optimal Inapproximability of Satisfiable $k$ -LIN over Non-Abelian Groups

A seminal result of Håstad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$ -LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant $\varepsilon>0$ . Engebretsen et al. [Theoretical Computer Science, 312(1):17--45, 2004] later showed that the same hardness result holds for $k$ -LIN instances over any finite non-abelian group. Unlike the abelian case, where we can efficiently find a solution if the instance is satisfiable, in the non-abelian case, it is NP-complete to decide if a given system of linear equations is satisfiable or not, as shown by Goldmann and Russell [Information and Computation, 178(1):253--262. 2002]. Surprisingly, for certain non-abelian groups $G$ , given a satisfiable $k$ -LIN instance over $G$ , one can in fact do better than just outputting a random assignment using a simple but clever algorithm. The approximation factor achieved by this algorithm varies with the underlying group. In this paper, we show that this algorithm is {\em optimal} by proving a tight hardness of approximation of satisfiable $k$ -LIN instance over {\em any} non-abelian $G$ , assuming $P \neq NP$ . As a corollary, we also get $3$ -query probabilistically checkable proofs with perfect completeness over large alphabets with improved soundness.

preprint2016arXiv

Cube vs. Cube Low Degree Test

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$ ) that intersect on a point $x\in \mathbf{F}^m$ , and checks that the assignments to the cubes agree with each other on the point $x$ . Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all $ε\ge poly(d)/{\mathbf{F}}^{1/2}$ , where $d$ is the degree. This should be compared to the previously best soundness value of $ε\ge poly(m, d)/\mathbf{F}^{1/8}$ . Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space. Our proof is combinatorial and direct: unlike the Raz-Safra proof, it proceeds in one shot and does not require induction on the dimension of the ambient space. The ideas in our proof come from works on direct product testing which are even simpler in the current setting thanks to the low degree. Along the way we also prove a somewhat surprising fact about connection between different agreement tests: it does not matter if the tester chooses the cubes to intersect on points or on lines: for every given table, its success probability in either test is nearly the same.

preprint2015arXiv

On Fortification of Projection Games

A recent result of Moshkovitz \cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both $\ell_1$ and $\ell_2$ guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters (the latter is also the construction used in an independent update \cite{Moshkovitz15} of \cite{Moshkovitz14} with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular $\ell_2$ guarantees) is necessary for obtaining the robustness required for fortification.

preprint2015arXiv

The complexity of computing the minimum rank of a sign pattern matrix

We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and the stretchability problem for pseudolines arrangements. In fact, our hardness result shows that it is already hard to determine if the minimum rank of a sign pattern matrix is $\leq 3$ . We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank $\leq 2$ . Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].

preprint2014arXiv

Simultaneous Approximation of Constraint Satisfaction Problems

Given $k$ collections of 2SAT clauses on the same set of variables $V$ , can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context. Our main result is that for every CSP $F$ , for $k < \tilde{O}(\log^{1/4} n)$ , there is a polynomial time constant factor Pareto approximation algorithm for $k$ simultaneous Max- $F$ -CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for $k <\tilde{O}(\log^{1/3} n)$ ). In contrast, for $k = ω(\log n)$ , no nonzero approximation factor for $k$ simultaneous Max- $F$ -CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis). These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.

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.

Amey Bhangale

Research overview

Is this your work?

7 publications

A Characterization of hard-to-cover CSPs

Hardness of Approximation of (Multi-)LCS over Small Alphabet

Optimal Inapproximability of Satisfiable $k$ -LIN over Non-Abelian Groups

Cube vs. Cube Low Degree Test

On Fortification of Projection Games

The complexity of computing the minimum rank of a sign pattern matrix

Simultaneous Approximation of Constraint Satisfaction Problems

See the researcher in context

Building this map preview

Amey Bhangale

Research overview

Is this your work?

7 publications

A Characterization of hard-to-cover CSPs

Hardness of Approximation of (Multi-)LCS over Small Alphabet

Optimal Inapproximability of Satisfiable kkk-LIN over Non-Abelian Groups

Cube vs. Cube Low Degree Test

On Fortification of Projection Games

The complexity of computing the minimum rank of a sign pattern matrix

Simultaneous Approximation of Constraint Satisfaction Problems

See the researcher in context

Building this map preview

Optimal Inapproximability of Satisfiable $k$ -LIN over Non-Abelian Groups