7 Search Results for "Liao, Zhenyu"

Document
DOI: 10.4230/OASIcs.NINeS.2026.19
Simulate Before Sending: Rethinking Transport in Datacenter Networks

Authors: Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Existing transport protocols in commodity datacenter networks struggle to provide low collective completion times (CCTs) to AI training collectives, as packet losses and retransmissions significantly degrade performance. We propose dcSim, an efficient transport that achieves low CCTs and practically lossless performance with commodity switches. In dcSim, each packet first employs a small simulation probe to traverse the network and explore congestion along a candidate path. Only packets whose simulation probes succeed are then transmitted, expecting to succeed as well. Evaluations confirm that dcSim achieves faster CCTs than existing schemes, with small queues and virtually zero packet loss. Finally, dcSim also excels in adverse conditions, including oversubscribed topologies.
Cite as

Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss. Simulate Before Sending: Rethinking Transport in Datacenter Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{straussman_et_al:OASIcs.NINeS.2026.19,
  author =	{Straussman, Dan and Keslassy, Isaac and Shpiner, Alexander and Liss, Liran},
  title =	{{Simulate Before Sending: Rethinking Transport in Datacenter Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{19:1--19:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.19},
  URN =		{urn:nbn:de:0030-drops-256044},
  doi =		{10.4230/OASIcs.NINeS.2026.19},
  annote =	{Keywords: Datacenter networks, transport protocols, AI training, lossless networks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.38
Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.
Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
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.55
Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity

Authors: Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong

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

Abstract
An oblivious subspace embedding is a random m× n matrix Π such that, for any d-dimensional subspace, with high probability Π preserves the norms of all vectors in that subspace within a 1±ε factor. In this work, we give an oblivious subspace embedding with the optimal dimension m = Θ(d/ε²) that has a near-optimal sparsity of Õ(1/ε) non-zero entries per column of Π. This is the first result to nearly match the conjecture of Nelson and Nguyen [FOCS 2013] in terms of the best sparsity attainable by an optimal oblivious subspace embedding, improving on a prior bound of Õ(1/ε⁶) non-zeros per column [Chenakkod et al., STOC 2024]. We further extend our approach to the non-oblivious setting, proposing a new family of Leverage Score Sparsified embeddings with Independent Columns, which yield faster runtimes for matrix approximation and regression tasks. In our analysis, we develop a new method which uses a decoupling argument together with the cumulant method for bounding the edge universality error of isotropic random matrices. To achieve near-optimal sparsity, we combine this general-purpose approach with new trace inequalities that leverage the specific structure of our subspace embedding construction.
Cite as

Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong. Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 55:1-55:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chenakkod_et_al:LIPIcs.ICALP.2025.55,
  author =	{Chenakkod, Shabarish and Derezi\'{n}ski, Micha{\l} and Dong, Xiaoyu},
  title =	{{Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{55:1--55:20},
  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.55},
  URN =		{urn:nbn:de:0030-drops-234324},
  doi =		{10.4230/LIPIcs.ICALP.2025.55},
  annote =	{Keywords: Randomized linear algebra, matrix sketching, subspace embeddings}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.83
Low-Temperature Sampling on Sparse Random Graphs

Authors: Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova

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

Abstract
We consider sampling in the so-called low-temperature regime, which is typically characterised by non-local behaviour and strong global correlations. Canonical examples include sampling independent sets on bipartite graphs and sampling from the ferromagnetic q-state Potts model. Low-temperature sampling is computationally intractable for general graphs, but recent advances based on the polymer method have made significant progress for graph families that exhibit certain expansion properties that reinforce the correlations, including for example expanders, lattices and dense graphs. One of the most natural graph classes that has so far escaped this algorithmic framework is the class of sparse Erdős-Rényi random graphs whose expansion only manifests for sufficiently large subsets of vertices; small sets of vertices on the other hand have vanishing expansion which makes them behave independently from the bulk of the graph and therefore weakens the correlations. At a more technical level, the expansion of small sets is crucial for establishing the Kotecky-Priess condition which underpins the applicability of the framework. Our main contribution is to develop the polymer method in the low-temperature regime for sparse random graphs. As our running example, we use the Potts and random-cluster models on G(n,d/n) for d = Θ(1), where we show a polynomial-time sampling algorithm for all sufficiently large q and d, at all temperatures. Our approach applies more generally for models that are monotone. Key to our result is a simple polymer definition that blends easily with the connectivity properties of the graph and allows us to show that polymers have size at most O(log n).
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Low-Temperature Sampling on Sparse Random Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.ICALP.2025.83,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Low-Temperature Sampling on Sparse Random Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{83:1--83:20},
  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.83},
  URN =		{urn:nbn:de:0030-drops-234606},
  doi =		{10.4230/LIPIcs.ICALP.2025.83},
  annote =	{Keywords: approximate counting, Glauber dynamics, random cluster model, approximate sampling, Erd\H{o}s-R\'{e}nyi Graphs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.34
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs

Authors: Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao

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

Abstract
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every Delta-regular bipartite graph if Delta >= 53. In the weighted case, for all sufficiently large integers Delta and weight parameters lambda = Omega~ (1/(Delta)), we also obtain an FPTAS on almost every Delta-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all q >= 3 and sufficiently large integers Delta=Delta(q), there is an FPTAS to count the number of q-colorings on almost every Delta-regular bipartite graph.
Cite as

Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting Independent Sets and Colorings on Random Regular Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liao_et_al:LIPIcs.APPROX-RANDOM.2019.34,
  author =	{Liao, Chao and Lin, Jiabao and Lu, Pinyan and Mao, Zhenyu},
  title =	{{Counting Independent Sets and Colorings on Random Regular Bipartite Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.34},
  URN =		{urn:nbn:de:0030-drops-112498},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.34},
  annote =	{Keywords: Approximate counting, Polymer model, Hardcore model, Coloring, Random bipartite graphs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.53
Optimization Algorithms for Faster Computational Geometry

Authors: Zeyuan Allen-Zhu, Zhenyu Liao, and Yang Yuan

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study two fundamental problems in computational geometry: finding the maximum inscribed ball (MaxIB) inside a bounded polyhedron defined by m hyperplanes, and the minimum enclosing ball (MinEB) of a set of n points, both in d-dimensional space. We improve the running time of iterative algorithms on MaxIB from ~O(m*d*alpha^3/epsilon^3) to ~O(m*d + m*sqrt(d)*alpha/epsilon), a speed-up up to ~O(sqrt(d)*alpha^2/epsilon^2), and MinEB from ~O(n*d/sqrt(epsilon)) to ~O(n*d + n*sqrt(d)/sqrt(epsilon)), a speed-up up to ~O(sqrt(d)). Our improvements are based on a novel saddle-point optimization framework. We propose a new algorithm L1L2SPSolver for solving a class of regularized saddle-point problems, and apply a randomized Hadamard space rotation which is a technique borrowed from compressive sensing. Interestingly, the motivation of using Hadamard rotation solely comes from our optimization view but not the original geometry problem: indeed, it is not immediately clear why MaxIB or MinEB, as a geometric problem, should be easier to solve if we rotate the space by a unitary matrix. We hope that our optimization perspective sheds lights on solving other geometric problems as well.
Cite as

Zeyuan Allen-Zhu, Zhenyu Liao, and Yang Yuan. Optimization Algorithms for Faster Computational Geometry. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 53:1-53:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{allenzhu_et_al:LIPIcs.ICALP.2016.53,
  author =	{Allen-Zhu, Zeyuan and Liao, Zhenyu and Yuan, Yang},
  title =	{{Optimization Algorithms for Faster Computational Geometry}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{53:1--53:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.53},
  URN =		{urn:nbn:de:0030-drops-63325},
  doi =		{10.4230/LIPIcs.ICALP.2016.53},
  annote =	{Keywords: maximum inscribed balls, minimum enclosing balls, approximation algorithms}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 3 2025
  • 1 2019
  • 1 2016

  • Refine by Author
  • 1 Allen-Zhu, Zeyuan
  • 1 Chen, Xiaoyu
  • 1 Chenakkod, Shabarish
  • 1 Dereziński, Michał
  • 1 Dong, Xiaoyu
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Mathematics of computing → Gibbs sampling
  • 1 Mathematics of computing → Markov-chain Monte Carlo methods
  • 1 Mathematics of computing → Random graphs
  • 1 Networks → Data center networks
  • 1 Networks → Transport protocols
  • Show More...

  • Refine by Keyword
  • 2 Glauber dynamics
  • 1 (Directed) hypergraphs
  • 1 AI training
  • 1 Approximate counting
  • 1 Coloring
  • 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