8 Search Results for "Oveis Gharan, Shayan"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.40
On Optimization and Counting of Non-Broken Bases of Matroids

Authors: Dorna Abdolazimi, Kasper Lindberg, and Shayan Oveis Gharan

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

Abstract
Given a matroid M = (E,I), and a total ordering over the elements E, a broken circuit is a circuit where the smallest element is removed and an NBC independent set is an independent set in I with no broken circuit. The set of NBC independent sets of any matroid M define a simplicial complex called the broken circuit complex which has been the subject of intense study in combinatorics. Recently, Adiprasito, Huh and Katz showed that the face of numbers of any broken circuit complex form a log-concave sequence, proving a long-standing conjecture of Rota. We study counting and optimization problems on NBC bases of a generic matroid. We find several fundamental differences with the independent set complex: for example, we show that it is NP-hard to find the max-weight NBC base of a matroid or that the convex hull of NBC bases of a matroid has edges of arbitrary large length. We also give evidence that the natural down-up walk on the space of NBC bases of a matroid may not mix rapidly by showing that for some family of matroids it is NP-hard to count the number of NBC bases after certain conditionings.
Cite as

Dorna Abdolazimi, Kasper Lindberg, and Shayan Oveis Gharan. On Optimization and Counting of Non-Broken Bases of Matroids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 40:1-40:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.APPROX/RANDOM.2023.40,
  author =	{Abdolazimi, Dorna and Lindberg, Kasper and Gharan, Shayan Oveis},
  title =	{{On Optimization and Counting of Non-Broken Bases of Matroids}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.40},
  URN =		{urn:nbn:de:0030-drops-188653},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.40},
  annote =	{Keywords: Complexity, Hardness, Optimization, Counting, Random walk, Local to Global, Matroids}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.10
An Improved Trickle down Theorem for Partite Complexes

Authors: Dorna Abdolazimi and Shayan Oveis Gharan

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

Abstract
We prove a strengthening of the trickle down theorem for partite complexes. Given a (d+1)-partite d-dimensional simplicial complex, we show that if "on average" the links of faces of co-dimension 2 are (1-δ)/d-(one-sided) spectral expanders, then the link of any face of co-dimension k is an O((1-δ)/(kδ))-(one-sided) spectral expander, for all 3 ≤ k ≤ d+1. For an application, using our theorem as a black-box, we show that links of faces of co-dimension k in recent constructions of bounded degree high dimensional expanders have spectral expansion at most O(1/k) fraction of the spectral expansion of the links of the worst faces of co-dimension 2.
Cite as

Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10,
  author =	{Abdolazimi, Dorna and Oveis Gharan, Shayan},
  title =	{{An Improved Trickle down Theorem for Partite Complexes}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.10},
  URN =		{urn:nbn:de:0030-drops-182807},
  doi =		{10.4230/LIPIcs.CCC.2023.10},
  annote =	{Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.1
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)

Authors: Anna R. Karlin

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We describe recent joint work with Nathan Klein and Shayan Oveis Gharan showing that for any metric TSP instance, the max entropy algorithm studied by [Anna R. Karlin et al., 2021] returns a solution of expected cost at most 3/2-ε times the cost of the optimal solution to the subtour elimination LP and hence is a 3/2-ε approximation for the metric TSP problem. The research discussed comes from [Anna R. Karlin et al., 2021], [Anna R. Karlin et al., 2022] and [Anna R. Karlin et al., 2022].
Cite as

Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{karlin:LIPIcs.ICALP.2023.1,
  author =	{Karlin, Anna R.},
  title =	{{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1},
  URN =		{urn:nbn:de:0030-drops-180531},
  doi =		{10.4230/LIPIcs.ICALP.2023.1},
  annote =	{Keywords: Traveling Salesperson Problem, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.2
Matroid Partition Property and the Secretary Problem

Authors: Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan

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

Abstract
A matroid M on a set E of elements has the α-partition property, for some α > 0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of M such that every independent set of 𝒫 is independent in M and for any weight function w:E → ℝ_{≥0}, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on M. We show that the complete binary matroid, B_d on 𝔽₂^d does not satisfy the α-partition property for any constant α > 0 (independent of d). Furthermore, we refute a recent conjecture of [Kristóf Bérczi et al., 2021] by showing the same matroid is 2^d/d-colorable but cannot be reduced to an α 2^d/d-colorable partition matroid for any α that is sublinear in d.
Cite as

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2,
  author =	{Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title =	{{Matroid Partition Property and the Secretary Problem}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{2:1--2:9},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-175051},
  doi =		{10.4230/LIPIcs.ITCS.2023.2},
  annote =	{Keywords: Online algorithms, Matroids, Matroid secretary problem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.61
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

Authors: Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in d-regular strong expander (non-bipartite) graphs, with 2n vertices, is a polynomial in n, thus the Jerrum and Sinclair Markov chain [Jerrum and Sinclair, 1989] mixes in polynomial time and generates an (almost) uniformly random perfect matching. Furthermore, we prove that such graphs have at least Ω(d)ⁿ many perfect matchings, thus proving the Lovasz-Plummer conjecture [L. Lovász and M.D. Plummer, 1986] for this family of graphs.
Cite as

Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.61,
  author =	{Ebrahimnejad, Farzam and Nagda, Ansh and Gharan, Shayan Oveis},
  title =	{{Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.61},
  URN =		{urn:nbn:de:0030-drops-156579},
  doi =		{10.4230/LIPIcs.ITCS.2022.61},
  annote =	{Keywords: perfect matchings, approximate sampling, approximate counting, expanders}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.32
From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk

Authors: Kuikui Liu

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

Abstract
We show that the existence of a "good" coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distance between successive iterates under the coupling to be summable, as opposed to being one-step contractive in the worst case. Combined with recent local-to-global arguments [Chen et al., 2021], we establish asymptotically optimal lower bounds on the standard and modified log-Sobolev constants for the Glauber dynamics for sampling from spin systems on bounded-degree graphs when a curvature condition [Ollivier, 2009] is satisfied. To achieve this, we use Stein’s method for Markov chains [Bresler and Nagaraj, 2019; Reinert and Ross, 2019] to show that a "good" coupling for a local Markov chain yields strong bounds on the spectral independence of the distribution in the sense of [Anari et al., 2020]. Our primary application is to sampling proper list-colorings on bounded-degree graphs. In particular, combining the coupling for the flip dynamics given by [Vigoda, 2000; Chen et al., 2019] with our techniques, we show optimal O(nlog n) mixing for the Glauber dynamics for sampling proper list-colorings on any bounded-degree graph with maximum degree Δ whenever the size of the color lists are at least ({11/6 - ε}) Δ, where ε ≈ 10^{-5} is small constant. While O(n²) mixing was already known before, our approach additionally yields Chernoff-type concentration bounds for Hamming Lipschitz functions in this regime, which was not known before. Our approach is markedly different from prior works establishing spectral independence for spin systems using spatial mixing [Anari et al., 2020; Z. {Chen} et al., 2020; Chen et al., 2021; Feng et al., 2021], which crucially is still open in this regime for proper list-colorings.
Cite as

Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 32:1-32:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.APPROX/RANDOM.2021.32,
  author =	{Liu, Kuikui},
  title =	{{From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.32},
  URN =		{urn:nbn:de:0030-drops-147259},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.32},
  annote =	{Keywords: Markov chains, Approximate counting, Spectral independence}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.41
Graph Clustering using Effective Resistance

Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan

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

Abstract
We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the effective resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Cite as

Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 41:1-41:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alev_et_al:LIPIcs.ITCS.2018.41,
  author =	{Alev, Vedat Levi and Anari, Nima and Lau, Lap Chi and Oveis Gharan, Shayan},
  title =	{{Graph Clustering using Effective Resistance}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{41:1--41: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.41},
  URN =		{urn:nbn:de:0030-drops-83696},
  doi =		{10.4230/LIPIcs.ITCS.2018.41},
  annote =	{Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.36
Nash Social Welfare, Matrix Permanent, and Stable Polynomials

Authors: Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
We study the problem of allocating m items to n agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective, breaking the 1/2e^(1/e) approximation factor of Cole and Gkatzelis. Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.
Cite as

Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 36:1-36:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.ITCS.2017.36,
  author =	{Anari, Nima and Oveis Gharan, Shayan and Saberi, Amin and Singh, Mohit},
  title =	{{Nash Social Welfare, Matrix Permanent, and Stable Polynomials}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.36},
  URN =		{urn:nbn:de:0030-drops-81489},
  doi =		{10.4230/LIPIcs.ITCS.2017.36},
  annote =	{Keywords: Nash Welfare, Permanent, Matching, Stable Polynomial, Randomized Algorithm, Saddle Point}
}
  • Refine by Author
  • 4 Oveis Gharan, Shayan
  • 3 Abdolazimi, Dorna
  • 2 Anari, Nima
  • 2 Gharan, Shayan Oveis
  • 2 Karlin, Anna R.
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Expander graphs and randomness extractors
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Markov-chain Monte Carlo methods
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 Matroids
  • 1 Approximate counting
  • 1 Bounded degree high dimensional expanders
  • 1 Complexity
  • 1 Conductance
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 4 2023
  • 1 2017
  • 1 2018
  • 1 2021
  • 1 2022

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