BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Amey Bhangale

Amey Bhangale contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Complexity

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

3 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access