6 Search Results for "Sah, Ashwin"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.68
Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree

Authors: Xiaoyu Chen and Weiming Feng

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

Abstract
We develop a new framework to prove the mixing or relaxation time for the Glauber dynamics on spin systems with unbounded degree. It works for general spin systems including both 2-spin and multi-spin systems. As applications for this approach: - We prove the optimal O(n) relaxation time for the Glauber dynamics of random q-list-coloring on an n-vertices triangle-tree graph with maximum degree Δ such that q/Δ > α^⋆, where α^⋆ ≈ 1.763 is the unique positive solution of the equation α = exp(1/α). This improves the n^{1+o(1)} relaxation time for Glauber dynamics obtained by the previous work of Jain, Pham, and Vuong (2022). Besides, our framework can also give a near-linear time sampling algorithm under the same condition. - We prove the optimal O(n) relaxation time and near-optimal Õ(n) mixing time for the Glauber dynamics on hardcore models with parameter λ in balanced bipartite graphs such that λ < λ_c(Δ_L) for the max degree Δ_L in left part and the max degree Δ_R of right part satisfies Δ_R = O(Δ_L). This improves the previous result by Chen, Liu, and Yin (2023). At the heart of our proof is the notion of coupling independence which allows us to consider multiple vertices as a huge single vertex with exponentially large domain and do a "coarse-grained" local-to-global argument on spin systems. The technique works for general (multi) spin systems and helps us obtain some new comparison results for Glauber dynamics.
Cite as

Xiaoyu Chen and Weiming Feng. Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.68,
  author =	{Chen, Xiaoyu and Feng, Weiming},
  title =	{{Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.68},
  URN =		{urn:nbn:de:0030-drops-244345},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.68},
  annote =	{Keywords: coupling independence, Glauber dynamics, mixing times, relaxation times, spin systems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.48
Improved Streaming Edge Coloring

Authors: Shiri Chechik, Hongyi Chen, and Tianyi Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains n vertices and has maximum vertex degree Δ, it is known that in the W-streaming model, an O(Δ²)-edge coloring can be computed deterministically with Õ(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ^{1.5})-edge coloring can be computed by a Õ(n)-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to Õ(Δ^{4/3+ε}) using space Õ(n) deterministically, for any constant ε > 0. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.
Cite as

Shiri Chechik, Hongyi Chen, and Tianyi Zhang. Improved Streaming Edge Coloring. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chechik_et_al:LIPIcs.ICALP.2025.48,
  author =	{Chechik, Shiri and Chen, Hongyi and Zhang, Tianyi},
  title =	{{Improved Streaming Edge Coloring}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.48},
  URN =		{urn:nbn:de:0030-drops-234257},
  doi =		{10.4230/LIPIcs.ICALP.2025.48},
  annote =	{Keywords: edge coloring, streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.24
Sampling List Packings

Authors: Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial attention. For list packing the setup is similar, but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. The existence of a list packing implies the existence of a list coloring, but the converse is false. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (FPRAS) based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree.
Cite as

Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee. Sampling List Packings. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{camrud_et_al:LIPIcs.ITCS.2025.24,
  author =	{Camrud, Evan and Davies, Ewan and Karduna, Alex and Lee, Holden},
  title =	{{Sampling List Packings}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-226528},
  doi =		{10.4230/LIPIcs.ITCS.2025.24},
  annote =	{Keywords: List packing, Graph colouring, Markov chains, Path coupling}
}
Document
DOI: 10.4230/LIPIcs.FORC.2024.1
Effects of Privacy-Inducing Noise on Welfare and Influence of Referendum Systems

Authors: Suat Evren and Praneeth Vepakomma

Published in: LIPIcs, Volume 295, 5th Symposium on Foundations of Responsible Computing (FORC 2024)

Abstract
Social choice functions help aggregate individual preferences while differentially private mechanisms provide formal privacy guarantees to release answers of queries operating on sensitive data. However, preserving differential privacy requires introducing noise to the system, and therefore may lead to undesired byproducts. Does an increase in the level of privacy for releasing the outputs of social choice functions increase or decrease the level of influence and welfare, and at what rate? In this paper, we mainly address this question in more precise terms in a referendum setting with two candidates when the celebrated randomized response mechanism is used. We show that the level of privacy is inversely proportional to society’s welfare and influence.
Cite as

Suat Evren and Praneeth Vepakomma. Effects of Privacy-Inducing Noise on Welfare and Influence of Referendum Systems. In 5th Symposium on Foundations of Responsible Computing (FORC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 295, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{evren_et_al:LIPIcs.FORC.2024.1,
  author =	{Evren, Suat and Vepakomma, Praneeth},
  title =	{{Effects of Privacy-Inducing Noise on Welfare and Influence of Referendum Systems}},
  booktitle =	{5th Symposium on Foundations of Responsible Computing (FORC 2024)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-319-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{295},
  editor =	{Rothblum, Guy N.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2024.1},
  URN =		{urn:nbn:de:0030-drops-200841},
  doi =		{10.4230/LIPIcs.FORC.2024.1},
  annote =	{Keywords: Welfare, influence, social choice functions, differential privacy, randomized response}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.101
A Gaussian Fixed Point Random Walk

Authors: Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney

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

Abstract
In this note, we design a discrete random walk on the real line which takes steps 0,±1 (and one with steps in {±1,2}) where at least 96% of the signs are ±1 in expectation, and which has 𝒩(0,1) as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk’s discrepancy result for partial colorings and ±1,2 signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.
Cite as

Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney. A Gaussian Fixed Point Random Walk. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 101:1-101:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2022.101,
  author =	{Liu, Yang P. and Sah, Ashwin and Sawhney, Mehtaab},
  title =	{{A Gaussian Fixed Point Random Walk}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{101:1--101:10},
  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.101},
  URN =		{urn:nbn:de:0030-drops-156975},
  doi =		{10.4230/LIPIcs.ITCS.2022.101},
  annote =	{Keywords: Discrepancy, Partial Coloring}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.50
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Authors: Abhijit S. Mudigonda and R. Ryan Williams

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

Abstract
A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the SAT problem and related problems within the polynomial-time hierarchy. For example, for the SAT problem, the state-of-the-art is that the problem cannot be solved by random-access machines in n^c time and n^o(1) space simultaneously for c < 2cos(π/7) ≈ 1.801. We extend this lower bound approach to the quantum and randomized domains. Combining Grover’s algorithm with components from SAT time-space lower bounds, we show that there are problems verifiable in O(n) time with quantum Merlin-Arthur protocols that cannot be solved in n^c time and n^o(1) space simultaneously for c < (3+√3)/2 ≈ 2.366, a super-quadratic time lower bound. This result and the prior work on SAT can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in O(n) time with (classical) Merlin-Arthur protocols that cannot be solved in n^c randomized time and O(log n) space simultaneously for c < 1.465, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to c < 1.5.
Cite as

Abhijit S. Mudigonda and R. Ryan Williams. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mudigonda_et_al:LIPIcs.ITCS.2021.50,
  author =	{Mudigonda, Abhijit S. and Williams, R. Ryan},
  title =	{{Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{50:1--50:20},
  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.50},
  URN =		{urn:nbn:de:0030-drops-135897},
  doi =		{10.4230/LIPIcs.ITCS.2021.50},
  annote =	{Keywords: Time-space tradeoffs, lower bounds, QMA}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2024
  • 1 2022
  • 1 2021

  • Refine by Author
  • 1 Camrud, Evan
  • 1 Chechik, Shiri
  • 1 Chen, Hongyi
  • 1 Chen, Xiaoyu
  • 1 Davies, Ewan
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Random walks and Markov chains
  • 1 Applied computing → Economics
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Security and privacy → Economics of security and privacy
  • Show More...

  • Refine by Keyword
  • 1 Discrepancy
  • 1 Glauber dynamics
  • 1 Graph colouring
  • 1 List packing
  • 1 Markov chains
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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