13 Search Results for "Vyas, Nikhil"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.34
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method

Authors: Lijie Chen

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In this paper, we obtain several new results on lower bounds and derandomization for ACC⁰ circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity): 1) We prove that any polynomial-time Merlin-Arthur proof system with an ACC⁰ verifier (denoted by MA_{ACC⁰}) can be simulated by a nondeterministic proof system with quasi-polynomial running time and polynomial proof length, on infinitely many input lengths. This improves the previous simulation by [Chen, Lyu, and Williams, FOCS 2020], which requires both quasi-polynomial running time and proof length. 2) We show that MA_{ACC⁰} cannot be computed by fixed-polynomial-size ACC⁰ circuits, and our hard languages are hard on a sufficiently dense set of input lengths. 3) We show that NEXP (nondeterministic exponential-time) does not have ACC⁰ circuits of sub-half-exponential size, improving the previous sub-third-exponential size lower bound for NEXP against ACC⁰ by [Williams, J. ACM 2014]. Combining our first and second results gives a conceptually simpler and derandomization-centric proof of the recent breakthrough result NQP := NTIME[2^polylog(n)] ̸ ⊂ ACC⁰ by [Murray and Williams, SICOMP 2020]: Instead of going through an easy witness lemma as they did, we first prove an ACC⁰ lower bound for a subclass of MA, and then derandomize that subclass into NQP, while retaining its hardness against ACC⁰. Moreover, since our derandomization of MA_{ACC⁰} achieves a polynomial proof length, we indeed prove that nondeterministic quasi-polynomial-time with n^ω(1) nondeterminism bits (denoted as NTIMEGUESS[2^polylog(n), n^ω(1)]) has no poly(n)-size ACC⁰ circuits, giving a new proof of a result by Vyas. Combining with a win-win argument based on randomized encodings from [Chen and Ren, STOC 2020], we also prove that NTIMEGUESS[2^polylog(n), n^ω(1)] cannot be 1/2+1/poly(n)-approximated by poly(n)-size ACC⁰ circuits, improving the recent strongly average-case lower bounds for NQP against ACC⁰ by [Chen and Ren, STOC 2020]. One interesting technical ingredient behind our second result is the construction of a PSPACE-complete language that is paddable, downward self-reducible, same-length checkable, and weakly error correctable. Moreover, all its reducibility properties have corresponding AC⁰[2] non-adaptive oracle circuits. Our construction builds and improves upon similar constructions from [Trevisan and Vadhan, Complexity 2007] and [Chen, FOCS 2019], which all require at least TC⁰ oracle circuits for implementing these properties.
Cite as

Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen:LIPIcs.ITCS.2023.34,
  author =	{Chen, Lijie},
  title =	{{New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.34},
  URN =		{urn:nbn:de:0030-drops-175373},
  doi =		{10.4230/LIPIcs.ITCS.2023.34},
  annote =	{Keywords: Circuit Lower Bounds, Derandomization, Algorithmic Method, ACC}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.99
On Oracles and Algorithmic Methods for Proving Lower Bounds

Authors: Nikhil Vyas and Ryan Williams

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions. 1) We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let Missing-String be the (total) search problem of producing a string that does not appear in a given list L containing M bit-strings of length N, where M < 2ⁿ. We show in a generic way how algorithms and uniform circuits (from restricted classes) for Missing-String imply complexity lower bounds (and in some cases, the converse holds as well). We give a local algorithm for Missing-String, which can compute any desired output bit making very few probes into the input, when the number of strings M is small enough. We apply this to prove a new nearly-optimal (up to oracles) time hierarchy theorem with advice. We show that the problem of constructing restricted uniform circuits for Missing-String is essentially equivalent to constructing functions without small non-uniform circuits, in a relativizing way. For example, we prove that small uniform depth-3 circuits for Missing-String would imply exponential circuit lower bounds for Σ₂ EXP, and depth-3 lower bounds for Missing-String would imply non-trivial circuits (relative to an oracle) for Σ₂ EXP problems. Both conclusions are longstanding open problems in circuit complexity. 2) It has been known since Impagliazzo, Kabanets, and Wigderson [JCSS 2002] that generic derandomizations improving subexponentially over exhaustive search would imply lower bounds such as NEXP ̸ ⊂ 𝖯/poly. Williams [SICOMP 2013] showed that Circuit-SAT algorithms running barely faster than exhaustive search would imply similar lower bounds. The known proofs of such results do not relativize (they use techniques from interactive proofs/PCPs). However, it has remained open whether there is an oracle under which the generic implications from circuit-analysis algorithms to circuit lower bounds fail. Building on an oracle of Fortnow, we construct an oracle relative to which the circuit approximation probability problem (CAPP) is in 𝖯, yet EXP^{NP} has polynomial-size circuits. We construct an oracle relative to which SAT can be solved in "half-exponential" time, yet exponential time (EXP) has polynomial-size circuits. Improving EXP to NEXP would give an oracle relative to which Σ₂ 𝖤 has "half-exponential" size circuits, which is open. (Recall it is known that Σ₂ 𝖤 is not in "sub-half-exponential" size, and the proof relativizes.) Moreover, the running time of the SAT algorithm cannot be improved: relative to all oracles, if SAT is in "sub-half-exponential" time then EXP does not have polynomial-size circuits.
Cite as

Nikhil Vyas and Ryan Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 99:1-99:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vyas_et_al:LIPIcs.ITCS.2023.99,
  author =	{Vyas, Nikhil and Williams, Ryan},
  title =	{{On Oracles and Algorithmic Methods for Proving Lower Bounds}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{99:1--99:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.99},
  URN =		{urn:nbn:de:0030-drops-176021},
  doi =		{10.4230/LIPIcs.ITCS.2023.99},
  annote =	{Keywords: oracles, relativization, circuit complexity, missing string, exponential hierarchy}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.48
On the Number of Quantifiers as a Complexity Measure

Authors: Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, and Ryan Williams

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
In 1981, Neil Immerman described a two-player game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in first-order logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al., 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express s-t connectivity, improving the previous known bound by a constant factor.
Cite as

Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, and Ryan Williams. On the Number of Quantifiers as a Complexity Measure. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fagin_et_al:LIPIcs.MFCS.2022.48,
  author =	{Fagin, Ronald and Lenchner, Jonathan and Vyas, Nikhil and Williams, Ryan},
  title =	{{On the Number of Quantifiers as a Complexity Measure}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.48},
  URN =		{urn:nbn:de:0030-drops-168460},
  doi =		{10.4230/LIPIcs.MFCS.2022.48},
  annote =	{Keywords: number of quantifiers, multi-structural games, complexity measure, s-t connectivity, trees, rooted trees}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.20
Optimal Fine-Grained Hardness of Approximation of Linear Equations

Authors: Mitali Bafna and Nikhil Vyas

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system (A,b), for A ∈ ℝ^{n×n} and b ∈ ℝⁿ, we wish to find a vector x ∈ ℝⁿ such that Ax = b. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time O(n^ω). We consider the problem of finding ε-approximate solutions to linear systems with respect to the L₂-norm, that is, given a satisfiable linear system (A ∈ ℝ^{n×n}, b ∈ ℝⁿ), find an x ∈ ℝⁿ such that ||Ax - b||₂ ≤ ε||b||₂. Our main result is a fine-grained reduction from computing the rank of a matrix to finding ε-approximate solutions to linear systems. In particular, if the best known Õ(n^ω) time algorithm for computing the rank of n × O(n) matrices is optimal (which we conjecture is true), then finding an ε-approximate solution to a dense linear system also requires Ω̃(n^ω) time, even for ε as large as (1 - 1/poly(n)). We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices and well-conditioned linear systems. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
Cite as

Mitali Bafna and Nikhil Vyas. Optimal Fine-Grained Hardness of Approximation of Linear Equations. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.ICALP.2021.20,
  author =	{Bafna, Mitali and Vyas, Nikhil},
  title =	{{Optimal Fine-Grained Hardness of Approximation of Linear Equations}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.20},
  URN =		{urn:nbn:de:0030-drops-140894},
  doi =		{10.4230/LIPIcs.ICALP.2021.20},
  annote =	{Keywords: Linear Equations, Fine-Grained Complexity, Hardness of Approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.78
Faster Random k-CNF Satisfiability

Authors: Andrea Lincoln and Adam Yedidia

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly. We build upon the algorithms of Schöning 1999 and Dantsin et al. in 2002. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^(n (1- Ω(1)/k))). Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^(n Ω(lg² k)/k), resulting in an overall runtime of O(2^(n (1- Ω(lg² k)/k))) for random k-SAT.
Cite as

Andrea Lincoln and Adam Yedidia. Faster Random k-CNF Satisfiability. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 78:1-78:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lincoln_et_al:LIPIcs.ICALP.2020.78,
  author =	{Lincoln, Andrea and Yedidia, Adam},
  title =	{{Faster Random k-CNF Satisfiability}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{78:1--78:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.78},
  URN =		{urn:nbn:de:0030-drops-124857},
  doi =		{10.4230/LIPIcs.ICALP.2020.78},
  annote =	{Keywords: Random k-SAT, Average-Case, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.37
Near-Optimal Complexity Bounds for Fragments of the Skolem Problem

Authors: S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Given a linear recurrence sequence (LRS), specified using the initial conditions and the recurrence relation, the Skolem problem asks if zero ever occurs in the infinite sequence generated by the LRS. Despite active research over last few decades, its decidability is known only for a few restricted subclasses, by either restricting the order of the LRS (upto 4) or by restricting the structure of the LRS (e.g., roots of its characteristic polynomial). In this paper, we identify a subclass of LRS of arbitrary order for which the Skolem problem is easy, namely LRS all of whose characteristic roots are (possibly complex) roots of real algebraic numbers, i.e., roots satisfying x^d = r for r real algebraic. We show that for this subclass, the Skolem problem can be solved in NP^RP. As a byproduct, we implicitly obtain effective bounds on the zero set of the LRS for this subclass. While prior works in this area often exploit deep results from algebraic and transcendental number theory to get such effective results, our techniques are primarily algorithmic and use linear algebra and Galois theory. We also complement our upper bounds with a NP lower bound for the Skolem problem via a new direct reduction from 3-CNF-SAT, matching the best known lower bounds.
Cite as

S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.STACS.2020.37,
  author =	{Akshay, S. and Balaji, Nikhil and Murhekar, Aniket and Varma, Rohith and Vyas, Nikhil},
  title =	{{Near-Optimal Complexity Bounds for Fragments of the Skolem Problem}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.37},
  URN =		{urn:nbn:de:0030-drops-118982},
  doi =		{10.4230/LIPIcs.STACS.2020.37},
  annote =	{Keywords: Linear Recurrences, Skolem problem, NP-completeness, Weighted automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.59
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

Authors: Nikhil Vyas and R. Ryan Williams

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in Quasi-NP = NTIME[n^{(log n)^O(1)}] and NEXP do not have small circuits (in the worst case and/or on average) from various circuit classes C, by showing that C admits non-trivial satisfiability and/or #SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of non-trivial #SAT algorithm for a circuit class {C}. Say a symmetric Boolean function f(x₁,…,x_n) is sparse if it outputs 1 on O(1) values of ∑_i x_i. We show that for every sparse f, and for all "typical" C, faster #SAT algorithms for C circuits actually imply lower bounds against the circuit class f ∘ C, which may be stronger than C itself. In particular: - #SAT algorithms for n^k-size C-circuits running in 2ⁿ/n^k time (for all k) imply NEXP does not have f ∘ C-circuits of polynomial size. - #SAT algorithms for 2^{n^ε}-size C-circuits running in 2^{n-n^ε} time (for some ε > 0) imply Quasi-NP does not have f ∘ C-circuits of polynomial size. Applying #SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMAJ ∘ ACC⁰ ∘ THR circuits of polynomial size, where EMAJ is the "exact majority" function, improving previous lower bounds against ACC⁰ [Williams JACM'14] and ACC⁰ ∘ THR [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class.
Cite as

Nikhil Vyas and R. Ryan Williams. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vyas_et_al:LIPIcs.STACS.2020.59,
  author =	{Vyas, Nikhil and Williams, R. Ryan},
  title =	{{Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.59},
  URN =		{urn:nbn:de:0030-drops-119200},
  doi =		{10.4230/LIPIcs.STACS.2020.59},
  annote =	{Keywords: #SAT, satisfiability, circuit complexity, exact majority, ACC}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.11
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs

Authors: Andrea Lincoln and Nikhil Vyas

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We consider space-efficient algorithms and conditional time lower bounds for finding cycles and walks in graphs. We give a reduction that connects the running time of undirected 2k-cycle to finding directed odd cycles, s-t connectivity in directed graphs, and Max-3-SAT. For example, we show that if 2k-cycle on O(n)-edge graphs can be solved in O(n^(1.5-ε)) time for some ε>0 then, a 2^(n(1-ε')) time algorithm exists for Max-3-SAT for some ε'>0. Additionally, we give a tight combinatorial lower bound for 2k-cycle detection, specifically when k is odd, of m^{2k/(k+1) +o(1)} given the Combinatorial k-Clique Hypothesis. On the algorithms side, we present a randomized algorithm for directed s-t connectivity using O(lg(n)^2) space and O(n^{lg(n)/2 + o(lg(n))}) expected time, giving a time improvement over Savitch’s famous algorithm, which takes at least n^{lg(n) - o(lg(n))} time. Under the conjecture that every O(lg(n)^2)-space algorithm for directed s-t connectivity requires n^Ω(lg(n)) time, we show that undirected 2k-cycle in O(lg(n)) space requires n^Ω(lg(k)) time.
Cite as

Andrea Lincoln and Nikhil Vyas. Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lincoln_et_al:LIPIcs.ITCS.2020.11,
  author =	{Lincoln, Andrea and Vyas, Nikhil},
  title =	{{Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.11},
  URN =		{urn:nbn:de:0030-drops-116969},
  doi =		{10.4230/LIPIcs.ITCS.2020.11},
  annote =	{Keywords: k-cycle, Space, Savitch, Sparse Graphs, Max-3-SAT}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.32
Imperfect Gaps in Gap-ETH and PCPs

Authors: Mitali Bafna and Nikhil Vyas

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a way to transform a PCP with imperfect completeness to one with perfect completeness, when the initial gap is a constant. We show that PCP_{c,s}[r,q] subseteq PCP_{1,s'}[r+O(1),q+O(r)] for c-s=Omega(1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NP with a O(log n) additive loss in the query complexity q. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs, (when completeness is not 1) analogous to questions studied in parallel repetition [Anup Rao, 2011] and pseudorandomness [David Gillman, 1998] and might be of independent interest. We also investigate the time-complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. MAX 3SAT(1-epsilon,1-delta), delta > epsilon has 2^{o(n)} algorithms if and only if MAX 3SAT(1,1-delta) has 2^{o(n)} algorithms. We also relate the time complexities of these two problems in a more fine-grained way to show that T_2(n) <= T_1(n(log log n)^{O(1)}), where T_1(n),T_2(n) denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness respectively.
Cite as

Mitali Bafna and Nikhil Vyas. Imperfect Gaps in Gap-ETH and PCPs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.CCC.2019.32,
  author =	{Bafna, Mitali and Vyas, Nikhil},
  title =	{{Imperfect Gaps in Gap-ETH and PCPs}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.32},
  URN =		{urn:nbn:de:0030-drops-108545},
  doi =		{10.4230/LIPIcs.CCC.2019.32},
  annote =	{Keywords: PCP, Gap-ETH, Hardness of Approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.46
Approximation Algorithms for Min-Distance Problems

Authors: Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance between u and v is the minimum of the shortest path distances from u to v and from v to u. The center node in a graph under this measure can for instance represent the optimal location for a hospital to ensure the fastest medical care for everyone, as one can either go to the hospital, or a doctor can be sent to help. By computing All-Pairs Shortest Paths, all pairwise distances and thus the parameters we study can be computed exactly in O~(mn) time for directed graphs on n vertices, m edges and nonnegative edge weights. Furthermore, this time bound is tight under the Strong Exponential Time Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how well these parameters can be approximated in O(mn^{1-epsilon}) time for constant epsilon>0. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave a polynomial factor approximation for Diameter and Radius, as well as a constant factor approximation for both problems in the special case where the graph is a DAG. We greatly improve upon these bounds by providing the first constant factor approximations for Diameter, Radius and the related Eccentricities problem in general graphs. Additionally, we provide a hierarchy of algorithms for Diameter that gives a time/accuracy trade-off.
Cite as

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.46,
  author =	{Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole and Xu, Yinzhan and Yu, Yuancheng},
  title =	{{Approximation Algorithms for Min-Distance Problems}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.46},
  URN =		{urn:nbn:de:0030-drops-106223},
  doi =		{10.4230/LIPIcs.ICALP.2019.46},
  annote =	{Keywords: fine-grained complexity, graph algorithms, diameter, radius, eccentricities}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.47
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems

Authors: Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node can reach all other nodes). The natural and important ST-variant considers two subsets S and T of the vertex set and lets the ST-diameter be the maximum distance between a node in S and a node in T, and the ST-radius be the minimum distance for a node of S to reach all nodes of T. The bichromatic variant is the special case in which S and T partition the vertex set. In this paper we present a comprehensive study of the approximability of ST and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis. For instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an O~(m^{3/2}) time 5/3-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.
Cite as

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.47,
  author =	{Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole},
  title =	{{Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.47},
  URN =		{urn:nbn:de:0030-drops-106238},
  doi =		{10.4230/LIPIcs.ICALP.2019.47},
  annote =	{Keywords: approximation algorithms, fine-grained complexity, diameter, radius, eccentricities}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.78
Complexity of Restricted Variants of Skolem and Related Problems

Authors: Akshay S., Nikhil Balaji, and Nikhil Vyas

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Given a linear recurrence sequence (LRS), the Skolem problem, asks whether it ever becomes zero. The decidability of this problem has been open for several decades. Currently decidability is known only for LRS of order upto 4. For arbitrary orders (i.e., number of terms the n-th depends on), the only known complexity result is NP-hardness by a result of Blondel and Portier from 2002. In this paper, we give a different proof of this hardness result, which is arguably simpler and pinpoints the source of hardness. To demonstrate this, we identify a subclass of LRS for which the Skolem problem is in fact NP-complete. We show the generic nature of our lower-bound technique by adapting it to show stronger lower bounds of a related problem that encompasses many known decision problems on linear recurrent sequences.
Cite as

Akshay S., Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{s._et_al:LIPIcs.MFCS.2017.78,
  author =	{S., Akshay and Balaji, Nikhil and Vyas, Nikhil},
  title =	{{Complexity of Restricted Variants of Skolem and Related Problems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.78},
  URN =		{urn:nbn:de:0030-drops-81306},
  doi =		{10.4230/LIPIcs.MFCS.2017.78},
  annote =	{Keywords: Linear recurrence sequences, Skolem problem, NP-completeness, Program termination}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.8
On Regularity of Unary Probabilistic Automata

Authors: S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
The quantitative verification of Probabilistic Automata (PA) is undecidable in general. Unary PA are a simpler model where the choice of action is fixed. Still, the quantitative verification problem is open and known to be as hard as Skolem's problem, a problem on linear recurrence sequences, whose decidability is open for at least 40 years. In this paper, we approach this problem by studying the languages generated by unary PAs (as defined below), whose regularity would entail the decidability of quantitative verification. Given an initial distribution, we represent the trajectory of a unary PA over time as an infinite word over a finite alphabet, where the n-th letter represents a probability range after n steps. We extend this to a language of trajectories (a set of words), one trajectory for each initial distribution from a (possibly infinite) set. We show that if the eigenvalues of the transition matrix associated with the unary PA are all distinct positive real numbers, then the language is effectively regular. Further, we show that this result is at the boundary of regularity, as non-regular languages can be generated when the restrictions are even slightly relaxed. The regular representation of the language allows us to reason about more general properties, e.g., robustness of a regular property in a neighbourhood around a given distribution.
Cite as

S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas. On Regularity of Unary Probabilistic Automata. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.STACS.2016.8,
  author =	{Akshay, S. and Genest, Blaise and Karelovic, Bruno and Vyas, Nikhil},
  title =	{{On Regularity of Unary Probabilistic Automata}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.8},
  URN =		{urn:nbn:de:0030-drops-57093},
  doi =		{10.4230/LIPIcs.STACS.2016.8},
  annote =	{Keywords: Probabilistic automata, Symbolic dynamics, Markov chains, Skolem problem, Regularity}
}
  • Refine by Author
  • 11 Vyas, Nikhil
  • 2 Akshay, S.
  • 2 Bafna, Mitali
  • 2 Balaji, Nikhil
  • 2 Dalirrooyfard, Mina
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Problems, reductions and completeness
  • 3 Theory of computation → Circuit complexity
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 3 Skolem problem
  • 2 ACC
  • 2 Hardness of Approximation
  • 2 NP-completeness
  • 2 circuit complexity
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 4 2020
  • 3 2019
  • 2 2023
  • 1 2016
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact