Document

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

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.

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

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

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.

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

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

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.

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

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

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.

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} }