13 Search Results for "Trevisan, Luca"

Document
DOI: 10.4230/LIPIcs.ESA.2023.72
Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths

Authors: Tomasz Kociumaka and Adam Polak

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman-Ford algorithm solves this problem in O(hm) time, where m is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with nonnegative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary h ∈ O(√m). Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction h ∈ O(√m). In other words, the O(hm) bound is tight for the entire space of parameters h, m, and n, where n is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm.
Cite as

Tomasz Kociumaka and Adam Polak. Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 72:1-72:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kociumaka_et_al:LIPIcs.ESA.2023.72,
  author =	{Kociumaka, Tomasz and Polak, Adam},
  title =	{{Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{72:1--72:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.72},
  URN =		{urn:nbn:de:0030-drops-187257},
  doi =		{10.4230/LIPIcs.ESA.2023.72},
  annote =	{Keywords: Fine-grained complexity, graph algorithms, lower bounds, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.27
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

Authors: Tommaso d'Orsi and Luca Trevisan

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We define a novel notion of "non-backtracking" matrix associated to any symmetric matrix, and we prove a "Ihara-Bass" type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with k variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a p fraction of assignments, if the instance contains n variables and n^{k/2} / ε² constraints, we can efficiently compute a certificate that the optimum satisfies at most a p+O_k(ε) fraction of constraints. Previously, this was known for even k, but for odd k one needed n^{k/2} (log n)^{O(1)} / ε² random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck’s inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is o(n^⌈k/2⌉) and the third one cannot work when the number of constraints is o(n^{k/2} √{log n}). We further apply our techniques to obtain a new PTAS finding assignments for k-CSP instances with n^{k/2} / ε² constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.
Cite as

Tommaso d'Orsi and Luca Trevisan. A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dorsi_et_al:LIPIcs.CCC.2023.27,
  author =	{d'Orsi, Tommaso and Trevisan, Luca},
  title =	{{A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.27},
  URN =		{urn:nbn:de:0030-drops-182979},
  doi =		{10.4230/LIPIcs.CCC.2023.27},
  annote =	{Keywords: CSP, k-XOR, strong refutation, sum-of-squares, tensor, graph, hypergraph, non-backtracking walk}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.3
Bond Percolation in Small-World Graphs with Power-Law Distribution

Authors: Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
Full-bond percolation with parameter p is the process in which, given a graph, for every edge independently, we keep the edge with probability p and delete it with probability 1-p. Bond percolation is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Moreover, the full-bond percolation is equivalent to the Reed-Frost process, a network version of SIR epidemic spreading. We consider one-dimensional power-law small-world graphs with parameter α obtained as the union of a cycle with additional long-range random edges: each pair of nodes {u,v} at distance L on the cycle is connected by a long-range edge {u,v}, with probability proportional to 1/L^α. Our analysis determines three phases for the percolation subgraph G_p of the small-world graph, depending on the value of α. - If α < 1, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in 𝒪(log n) hops; - If 1 < α < 2, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in log^{𝒪(1)}(n) hops; - If α > 2, for every p < 1, with high probability all connected components of G_p have size 𝒪(log n).
Cite as

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi. Bond Percolation in Small-World Graphs with Power-Law Distribution. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.SAND.2023.3,
  author =	{Becchetti, Luca and Clementi, Andrea and Pasquale, Francesco and Trevisan, Luca and Ziccardi, Isabella},
  title =	{{Bond Percolation in Small-World Graphs with Power-Law Distribution}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.3},
  URN =		{urn:nbn:de:0030-drops-179392},
  doi =		{10.4230/LIPIcs.SAND.2023.3},
  annote =	{Keywords: Information spreading, gossiping, epidemics, fault-tolerance, network self-organization and formation, complex systems, social and transportation networks}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.34
Improved Pseudorandom Generators for AC⁰ Circuits

Authors: Xin Lyu

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We give PRG for depth-d, size-m AC⁰ circuits with seed length O(log^{d-1}(m)log(m/ε)log log(m)). Our PRG improves on previous work [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021] from various aspects. It has optimal dependence on 1/ε and is only one "log log(m)" away from the lower bound barrier. For the case of d = 2, the seed length tightly matches the best-known PRG for CNFs [Anindya De et al., 2010; Avishay Tal, 2017]. There are two technical ingredients behind our new result; both of them might be of independent interest. First, we use a partitioning-based approach to construct PRGs based on restriction lemmas for AC⁰. Previous works [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021] usually built PRGs on the Ajtai-Wigderson framework [Miklós Ajtai and Avi Wigderson, 1989]. Compared with them, the partitioning approach avoids the extra "log(n)" factor that usually arises from the Ajtai-Wigderson framework, allowing us to get the almost-tight seed length. The partitioning approach is quite general, and we believe it can help design PRGs for classes beyond constant-depth circuits. Second, improving and extending [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021], we prove a full derandomization of the powerful multi-switching lemma [Johan Håstad, 2014]. We show that one can use a short random seed to sample a restriction, such that a family of DNFs simultaneously simplifies under the restriction with high probability. This answers an open question in [Zander Kelley, 2021]. Previous derandomizations were either partial (that is, they pseudorandomly choose variables to restrict, and then fix those variables to truly-random bits) or had sub-optimal seed length. In our application, having a fully-derandomized switching lemma is crucial, and the randomness-efficiency of our derandomization allows us to get an almost-tight seed length.
Cite as

Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lyu:LIPIcs.CCC.2022.34,
  author =	{Lyu, Xin},
  title =	{{Improved Pseudorandom Generators for AC⁰ Circuits}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{34:1--34:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.34},
  URN =		{urn:nbn:de:0030-drops-165963},
  doi =		{10.4230/LIPIcs.CCC.2022.34},
  annote =	{Keywords: pseudorandom generators, derandomization, switching Lemmas, AC⁰}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.8
Lower Bounds for Function Inversion with Quantum Advice

Authors: Kai-Min Chung, Tai-Ning Liao, and Luowen Qian

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Function inversion is the problem that given a random function f: [M] → [N], we want to find pre-image of any image f^{-1}(y) in time T. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size S that only depends on f but not on y. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover’s algorithm [Grover, 1996], which does not leverage the power of preprocessing. Nayebi et al. [Nayebi et al., 2015] proved a lower bound ST² ≥ ̃Ω(N) for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. [Minki Hhan et al., 2019] subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where M = O(N). In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al. [Ambainis et al., 1999], to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
Cite as

Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower Bounds for Function Inversion with Quantum Advice. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ITC.2020.8,
  author =	{Chung, Kai-Min and Liao, Tai-Ning and Qian, Luowen},
  title =	{{Lower Bounds for Function Inversion with Quantum Advice}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.8},
  URN =		{urn:nbn:de:0030-drops-121134},
  doi =		{10.4230/LIPIcs.ITC.2020.8},
  annote =	{Keywords: Cryptanalysis, Data Structures, Quantum Query Complexity}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2020.42
Consensus vs Broadcast, with and Without Noise (Extended Abstract)

Authors: Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, and Luca Trevisan

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

Abstract
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.
Cite as

Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, and Luca Trevisan. Consensus vs Broadcast, with and Without Noise (Extended Abstract). In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.ITCS.2020.42,
  author =	{Clementi, Andrea and Gual\`{a}, Luciano and Natale, Emanuele and Pasquale, Francesco and Scornavacca, Giacomo and Trevisan, Luca},
  title =	{{Consensus vs Broadcast, with and Without Noise}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{42:1--42:13},
  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.42},
  URN =		{urn:nbn:de:0030-drops-117277},
  doi =		{10.4230/LIPIcs.ITCS.2020.42},
  annote =	{Keywords: Distributed Computing, Consensus, Broadcast, Gossip Models, Noisy Communication Channels}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.85
Combinatorial Lower Bounds for 3-Query LDCs

Authors: Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal

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

Abstract
A code is called a q-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index i and a received word w close to an encoding of a message x, outputs x_i by querying only at most q coordinates of w. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for 3-query binary LDC’s of dimension k and length n, the best known bounds are: 2^{k^o(1)} ≥ n ≥ Ω ̃(k²). In this work, we take a second look at binary 3-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of Ω ̃(k²) for the length of strong 3-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to 2-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.
Cite as

Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.ITCS.2020.85,
  author =	{Bhattacharyya, Arnab and Chandran, L. Sunil and Ghoshal, Suprovat},
  title =	{{Combinatorial Lower Bounds for 3-Query LDCs}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{85:1--85:8},
  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.85},
  URN =		{urn:nbn:de:0030-drops-117704},
  doi =		{10.4230/LIPIcs.ITCS.2020.85},
  annote =	{Keywords: Coding theory, Graph theory, Hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.71
Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Authors: Huan Li, He Sun, and Luca Zanetti

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.
Cite as

Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2019.71,
  author =	{Li, Huan and Sun, He and Zanetti, Luca},
  title =	{{Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.71},
  URN =		{urn:nbn:de:0030-drops-111926},
  doi =		{10.4230/LIPIcs.ESA.2019.71},
  annote =	{Keywords: Spectral methods, Hermitian Laplacians, the Max-2-Lin problem, Unique Games}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.8
Sherali - Adams Strikes Back

Authors: Ryan O'Donnell and Tselil Schramm

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

Abstract
Let G be any n-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1/sqrt{Delta} (for example, a random graph G of average degree Theta(Delta) typically has this property). We show that the exp(c (log n)/(log Delta))-round Sherali - Adams linear programming hierarchy certifies that the maximum cut in such a G is at most 50.1 % (in fact, at most 1/2 + 2^{-Omega(c)}). For example, in random graphs with n^{1.01} edges, O(1) rounds suffice; in random graphs with n * polylog(n) edges, n^{O(1/log log n)} = n^{o(1)} rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for max-cut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali - Adams can strongly refute random Boolean k-CSP instances with n^{ceil[k/2] + delta} constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.
Cite as

Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.CCC.2019.8,
  author =	{O'Donnell, Ryan and Schramm, Tselil},
  title =	{{Sherali - Adams Strikes Back}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{8:1--8:30},
  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.8},
  URN =		{urn:nbn:de:0030-drops-108309},
  doi =		{10.4230/LIPIcs.CCC.2019.8},
  annote =	{Keywords: Linear programming, Sherali, Adams, max-cut, graph eigenvalues, Sum-of-Squares}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.7
Average Whenever You Meet: Opportunistic Protocols for Community Detection

Authors: Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Consider the following asynchronous, opportunistic communication model over a graph G: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say +/- 1 with probability 1/2; then, in each round, the two endpoints of the currently active edge update their values to their average. We provide a rigorous analysis of the above process showing that, if G exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process. Our analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest. We then exploit our analysis to design the first opportunistic protocols that approximately recover community structure using only logarithmic (or polylogarithmic, depending on the sparsity of the cut) work per node.
Cite as

Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Average Whenever You Meet: Opportunistic Protocols for Community Detection. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ESA.2018.7,
  author =	{Becchetti, Luca and Clementi, Andrea and Manurangsi, Pasin and Natale, Emanuele and Pasquale, Francesco and Raghavendra, Prasad and Trevisan, Luca},
  title =	{{Average Whenever You Meet: Opportunistic Protocols for Community Detection}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.7},
  URN =		{urn:nbn:de:0030-drops-94705},
  doi =		{10.4230/LIPIcs.ESA.2018.7},
  annote =	{Keywords: Community Detection, Random Processes, Spectral Analysis}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.20
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut

Authors: Pasin Manurangsi and Luca Trevisan

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
In this work, we study the trade-off between the running time of approximation algorithms and their approximation guarantees. By leveraging a structure of the "hard" instances of the Arora-Rao-Vazirani lemma [Sanjeev Arora et al., 2009; James R. Lee, 2005], we show that the Sum-of-Squares hierarchy can be adapted to provide "fast", but still exponential time, approximation algorithms for several problems in the regime where they are believed to be NP-hard. Specifically, our framework yields the following algorithms; here n denote the number of vertices of the graph and r can be any positive real number greater than 1 (possibly depending on n). - A (2 - 1/(O(r)))-approximation algorithm for Vertex Cover that runs in exp (n/(2^{r^2)})n^{O(1)} time. - An O(r)-approximation algorithms for Uniform Sparsest Cut and Balanced Separator that runs in exp (n/(2^{r^2)})n^{O(1)} time. Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm [Nikhil Bansal et al., 2017] which achieves (2 - 1/(O(r)))-approximation in time exp (n/(r^r))n^{O(1)}. For Uniform Sparsest Cut and Balanced Separator, our algorithms improve upon O(r)-approximation exp (n/(2^r))n^{O(1)}-time algorithms that follow from a work of Charikar et al. [Moses Charikar et al., 2010].
Cite as

Pasin Manurangsi and Luca Trevisan. Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{manurangsi_et_al:LIPIcs.APPROX-RANDOM.2018.20,
  author =	{Manurangsi, Pasin and Trevisan, Luca},
  title =	{{Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.20},
  URN =		{urn:nbn:de:0030-drops-94241},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.20},
  annote =	{Keywords: Approximation algorithms, Exponential-time algorithms, Vertex Cover, Sparsest Cut, Balanced Separator}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.15
Near-Optimal UGC-hardness of Approximating Max k-CSP_R

Authors: Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
In this paper, we prove an almost-optimal hardness for Max k-CSP_R based on Khot's Unique Games Conjecture (UGC). In Max k-CSP_R, we are given a set of predicates each of which depends on exactly k variables. Each variable can take any value from 1, 2, ..., R. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max k-CSP_R to within factor 2^{O(k log k)}(log R)^{k/2}/R^{k - 1} for any k, R. To the best of our knowledge, this result improves on all the known hardness of approximation results when 3 <= k = o(log R/log log R). In this case, the previous best hardness result was NP-hardness of approximating within a factor O(k/R^{k-2}) by Chan. When k = 2, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP_R by Kindler, Kolla and Trevisan, we provide an Omega(log R/R^{k - 1})-approximation algorithm for Max k-CSP_R. This algorithm implies that our inapproximability result is tight up to a factor of 2^{O(k \log k)}(\log R)^{k/2 - 1}. In comparison, when 3 <= k is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of O(polylog R). Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's d-to-1 Conjecture and still get asymptotically the same hardness of approximation.
Cite as

Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-Optimal UGC-hardness of Approximating Max k-CSP_R. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 15:1-15:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{manurangsi_et_al:LIPIcs.APPROX-RANDOM.2016.15,
  author =	{Manurangsi, Pasin and Nakkiran, Preetum and Trevisan, Luca},
  title =	{{Near-Optimal UGC-hardness of Approximating Max k-CSP\underlineR}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{15:1--15:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.15},
  URN =		{urn:nbn:de:0030-drops-66388},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.15},
  annote =	{Keywords: inapproximability, unique games conjecture, constraint satisfaction problem, invariance principle}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.110
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Authors: Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.
Cite as

Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 110-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.APPROX-RANDOM.2015.110,
  author =	{Barak, Boaz and Moitra, Ankur and O’Donnell, Ryan and Raghavendra, Prasad and Regev, Oded and Steurer, David and Trevisan, Luca and Vijayaraghavan, Aravindan and Witmer, David and Wright, John},
  title =	{{Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{110--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  URN =		{urn:nbn:de:0030-drops-52981},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  annote =	{Keywords: constraint satisfaction problems, bounded degree, advantage over random}
}
  • Refine by Author
  • 7 Trevisan, Luca
  • 3 Clementi, Andrea
  • 3 Manurangsi, Pasin
  • 3 Pasquale, Francesco
  • 2 Becchetti, Luca
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Random network models
  • 1 Mathematics of computing → Probability and statistics
  • 1 Mathematics of computing → Spectra of graphs
  • Show More...

  • Refine by Keyword
  • 1 AC⁰
  • 1 Adams
  • 1 Approximation algorithms
  • 1 Balanced Separator
  • 1 Broadcast
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 3 2020
  • 3 2023
  • 2 2018
  • 2 2019
  • 1 2015
  • 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