10 Search Results for "Schramm, Tselil"

Document
DOI: 10.4230/LIPIcs.CCC.2022.11
Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance

Authors: Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu

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

Abstract
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the density, for which a precise landscape of predictions has been made via statistical physics-based heuristics. In parallel, there has been a recent flurry of work on refuting random constraint satisfaction problems, via nailing refutation thresholds for spectral and semidefinite programming-based algorithms, and also on counting solutions to CSPs. Inspired by this, the starting point for our work is the following question: What does the solution space for a random CSP look like to an efficient algorithm? In pursuit of this inquiry, we focus on the following problems about random Boolean CSPs at the densities where they are unsatisfiable but no refutation algorithm is known. 1) Counts. For every Boolean CSP we give algorithms that with high probability certify a subexponential upper bound on the number of solutions. We also give algorithms to certify a bound on the number of large cuts in a Gaussian-weighted graph, and the number of large independent sets in a random d-regular graph. 2) Clusters. For Boolean 3CSPs we give algorithms that with high probability certify an upper bound on the number of clusters of solutions. 3) Balance. We also give algorithms that with high probability certify that there are no "unbalanced" solutions, i.e., solutions where the fraction of +1s deviates significantly from 50%. Finally, we also provide hardness evidence suggesting that our algorithms for counting are optimal.
Cite as

Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu. Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 11:1-11:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hsieh_et_al:LIPIcs.CCC.2022.11,
  author =	{Hsieh, Jun-Ting and Mohanty, Sidhanth and Xu, Jeff},
  title =	{{Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{11:1--11:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.11},
  URN =		{urn:nbn:de:0030-drops-165735},
  doi =		{10.4230/LIPIcs.CCC.2022.11},
  annote =	{Keywords: constraint satisfaction problems, certified counting, random graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.97
The SDP Value of Random 2CSPs

Authors: Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over {±1}ⁿ. For each model ℳ, we identify the "high-probability value" s^*_ℳ of the natural SDP relaxation (equivalently, the quantum value). That is, for all ε > 0 we show that the SDP optimum of a random n-variable instance is (when normalized by n) in the range (s^*_ℳ-ε, s^*_ℳ+ε) with high probability. Our class of models includes non-regular CSPs, and ones where the SDP relaxation value is strictly smaller than the spectral relaxation value.
Cite as

Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu. The SDP Value of Random 2CSPs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 97:1-97:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{musipatla_et_al:LIPIcs.ICALP.2022.97,
  author =	{Musipatla, Amulya and O'Donnell, Ryan and Schramm, Tselil and Wu, Xinyu},
  title =	{{The SDP Value of Random 2CSPs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{97:1--97:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.97},
  URN =		{urn:nbn:de:0030-drops-164381},
  doi =		{10.4230/LIPIcs.ICALP.2022.97},
  annote =	{Keywords: Random constraint satisfaction problems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.10
The Strongish Planted Clique Hypothesis and Its Consequences

Authors: Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time n^Ω(log n) (so that the state-of-the-art running time of n^O(log n) is optimal up to a constant in the exponent). We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter k: Densest k-Subgraph, Smallest k-Edge Subgraph, Densest k-Subhypergraph, Steiner k-Forest, and Directed Steiner Network with k terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves o(k)-approximation for Densest k-Subgraph. This inapproximability ratio improves upon the previous best k^o(1) factor from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable algorithms with parameter k. Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, improving the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis.
Cite as

Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 10:1-10:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{manurangsi_et_al:LIPIcs.ITCS.2021.10,
  author =	{Manurangsi, Pasin and Rubinstein, Aviad and Schramm, Tselil},
  title =	{{The Strongish Planted Clique Hypothesis and Its Consequences}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.10},
  URN =		{urn:nbn:de:0030-drops-135491},
  doi =		{10.4230/LIPIcs.ITCS.2021.10},
  annote =	{Keywords: Planted Clique, Densest k-Subgraph, Hardness of Approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.39
Spectral Sparsification via Bounded-Independence Sampling

Authors: Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman

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

Abstract
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph G on n vertices described by a binary string of length N, an integer k ≤ log n and an error parameter ε > 0, our algorithm runs in space Õ(k log(N w_max/w_min)) where w_max and w_min are the maximum and minimum edge weights in G, and produces a weighted graph H with Õ(n^(1+2/k)/ε²) edges that spectrally approximates G, in the sense of Spielmen and Teng [Spielman and Teng, 2004], up to an error of ε. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastava’s effective resistance based edge sampling algorithm [Spielman and Srivastava, 2011] and uses results from recent work on space-bounded Laplacian solvers [Jack Murtagh et al., 2017]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by k above, and the resulting sparsity that can be achieved.
Cite as

Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.ICALP.2020.39,
  author =	{Doron, Dean and Murtagh, Jack and Vadhan, Salil and Zuckerman, David},
  title =	{{Spectral Sparsification via Bounded-Independence Sampling}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{39:1--39:21},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39},
  URN =		{urn:nbn:de:0030-drops-124462},
  doi =		{10.4230/LIPIcs.ICALP.2020.39},
  annote =	{Keywords: Spectral sparsification, Derandomization, Space complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.50
The SDP Value for Random Two-Eigenvalue CSPs

Authors: Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes

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

Abstract
We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, "two-eigenvalue 2CSPs". We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular 2XOR and NAE-3SAT, and includes new cases such as random Sort₄ (equivalently, CHSH) and Forrelation CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara-Bass Formula, and the Friedman/Bordenave proof of Alon’s Conjecture.
Cite as

Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. The SDP Value for Random Two-Eigenvalue CSPs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 50:1-50:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mohanty_et_al:LIPIcs.STACS.2020.50,
  author =	{Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro},
  title =	{{The SDP Value for Random Two-Eigenvalue CSPs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{50:1--50:45},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.50},
  URN =		{urn:nbn:de:0030-drops-119110},
  doi =		{10.4230/LIPIcs.STACS.2020.50},
  annote =	{Keywords: Semidefinite programming, constraint satisfaction problems}
}
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.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.ITCS.2019.49
SOS Lower Bounds with Hard Constraints: Think Global, Act Local

Authors: Pravesh K. Kothari, Ryan O'Donnell, and Tselil Schramm

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in, say, the Min-Bisection problem. Second, while the pseudoexpectation of the objective function was shown to have some value beta, it did not necessarily actually "satisfy" the constraint "objective = beta". In this paper we show how to remedy both deficiencies in the case of random CSPs, by translating global constraints into local constraints. Using these ideas, we also show that degree-Omega(sqrt{n}) SOS does not provide a (4/3 - epsilon)-approximation for Min-Bisection, and degree-Omega(n) SOS does not provide a (11/12 + epsilon)-approximation for Max-Bisection or a (5/4 - epsilon)-approximation for Min-Bisection. No prior SOS lower bounds for these problems were known.
Cite as

Pravesh K. Kothari, Ryan O'Donnell, and Tselil Schramm. SOS Lower Bounds with Hard Constraints: Think Global, Act Local. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 49:1-49:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kothari_et_al:LIPIcs.ITCS.2019.49,
  author =	{Kothari, Pravesh K. and O'Donnell, Ryan and Schramm, Tselil},
  title =	{{SOS Lower Bounds with Hard Constraints: Think Global, Act Local}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{49:1--49:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.49},
  URN =		{urn:nbn:de:0030-drops-101420},
  doi =		{10.4230/LIPIcs.ITCS.2019.49},
  annote =	{Keywords: sum-of-squares hierarchy, random constraint satisfaction problems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.39
Computing Exact Minimum Cuts Without Knowing the Graph

Authors: Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S \subset V, the oracle returns the size of the cut between S and V \ S. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while learning the graph requires ~{\Theta}(n^2) queries).
Cite as

Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2018.39,
  author =	{Rubinstein, Aviad and Schramm, Tselil and Weinberg, S. Matthew},
  title =	{{Computing Exact Minimum Cuts Without Knowing the Graph}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.39},
  URN =		{urn:nbn:de:0030-drops-83168},
  doi =		{10.4230/LIPIcs.ITCS.2018.39},
  annote =	{Keywords: query complexity, minimum cut}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.381
Gap Amplification for Small-Set Expansion via Random Walks

Authors: Prasad Raghavendra and Tselil Schramm

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

Abstract
In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness epsilon and soundness 1/2 is at least as difficult as Small-Set Expansion with completeness epsilon and soundness f(epsilon), for any function f(epsilon) which grows faster than (epsilon)^(1/2). We achieve this amplification via random walks--the output graph corresponds to taking random walks on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.
Cite as

Prasad Raghavendra and Tselil Schramm. Gap Amplification for Small-Set Expansion via Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 381-391, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{raghavendra_et_al:LIPIcs.APPROX-RANDOM.2014.381,
  author =	{Raghavendra, Prasad and Schramm, Tselil},
  title =	{{Gap Amplification for Small-Set Expansion via Random Walks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{381--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.381},
  URN =		{urn:nbn:de:0030-drops-47108},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.381},
  annote =	{Keywords: Gap amplification, Small-Set Expansion, random walks, graph products, Unique Games}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.779
Global and Local Information in Clustering Labeled Block Models

Authors: Varun Kanade, Elchanan Mossel, and Tselil Schramm

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

Abstract
The stochastic block model is a classical cluster-exhibiting random graph model that has been widely studied in statistics, physics and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intra-cluster edge probability p, and inter-cluster edge probability q. We focus on the sparse case, i.e. p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore and Zdeborova, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction of the conjecture was proved by Mossel, Neeman and Sly (2012), and more recently the positive direction was proven independently by Massoulie and Mossel, Neeman, and Sly. In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).
Cite as

Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and Local Information in Clustering Labeled Block Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 779-792, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2014.779,
  author =	{Kanade, Varun and Mossel, Elchanan and Schramm, Tselil},
  title =	{{Global and Local Information in Clustering Labeled Block Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{779--792},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.779},
  URN =		{urn:nbn:de:0030-drops-47384},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.779},
  annote =	{Keywords: stochastic block models, information flow on trees}
}
  • Refine by Author
  • 7 Schramm, Tselil
  • 4 O'Donnell, Ryan
  • 2 Mohanty, Sidhanth
  • 2 Rubinstein, Aviad
  • 1 Doron, Dean
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Semidefinite programming
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 constraint satisfaction problems
  • 1 Adams
  • 1 Densest k-Subgraph
  • 1 Derandomization
  • 1 Gap amplification
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2014
  • 2 2019
  • 2 2020
  • 2 2022
  • 1 2018
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact