Lap Chi Lau

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Spectral Sparsification by Deterministic Discrepancy Walk.

[BibT_eX]

[DOI]

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Streaming and Communication Complexity of Load-Balancing via Matching Contractors.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues.

[BibT_eX]

[DOI]

Kam Chuen Tung

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On the Houdré-Tetali Conjecture About an Isoperimetric Constant of Graphs.

[BibT_eX]

[DOI]

Dante Tjowasi

Proceedings of the Approximation, 2024

2023

Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues.

[BibT_eX]

[DOI]

Kam Chuen Tung

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Experimental Design for Any p-Norm.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Network Design for <i>s</i>-<i>t</i> Effective Resistance.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues.

[BibT_eX]

[DOI]

Kam Chuen Tung

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Local Search Framework for Experimental Design.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

A spectral approach to network design.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Improved analysis of higher order random walks and applications.

[BibT_eX]

[DOI]

Vedat Levi Alev

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Network design for s-t effective resistance.

[BibT_eX]

[DOI]

CoRR, 2019

Spectral Analysis of Matrix Scaling and Operator Scaling.

[BibT_eX]

[DOI]

Akshay Ramachandran

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

The Paulsen problem, continuous operator scaling, and smoothed analysis.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Graph Clustering using Effective Resistance.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Random Walks and Evolving Sets: Faster Convergences and Limitations.

[BibT_eX]

[DOI]

Siu On Chan

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating Unique Games Using Low Diameter Graph Decomposition.

[BibT_eX]

[DOI]

Vedat Levi Alev

Proceedings of the Approximation, 2017

2016

Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile.

[BibT_eX]

[DOI]

Yin Tat Lee

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2014

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

A Unified Algorithm for Degree Bounded Survivable Network Design.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Lower Bounds on Expansions of Graph Powers.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Finding Small Sparse Cuts Locally by Random Walk

[BibT_eX]

[DOI]

CoRR, 2012

Complexity of Finding Graph Roots with Girth Conditions.

[BibT_eX]

[DOI]

Algorithmica, 2012

Fast matrix rank algorithms and applications.

[BibT_eX]

[DOI]

Ho Yee Cheung

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Finding Small Sparse Cuts by Random Walk.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On Disjoint Common Bases in Two Matroids.

[BibT_eX]

[DOI]

Nicholas J. A. Harvey

SIAM J. Discret. Math., 2011

Algebraic Algorithms for Linear Matroid Parity Problems.

[BibT_eX]

[DOI]

Ho Yee Cheung

Kai Man Leung

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Degree Bounded Forest Covering.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Graph Connectivities, Network Coding, and Expander Graphs.

[BibT_eX]

[DOI]

Ho Yee Cheung

Kai Man Leung

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

On Linear and Semidefinite Programming Relaxations for Hypergraph Matching.

[BibT_eX]

[DOI]

Yuk Hei Chan

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities.

[BibT_eX]

[DOI]

Chun Kong Yung

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks.

[BibT_eX]

[DOI]

Zongpeng Li

Baochun Li

IEEE Trans. Inf. Theory, 2009

Computing Graph Roots Without Short Cycles.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2008

A note on degree-constrained subgraphs.

[BibT_eX]

[DOI]

András Frank

Jácint Szabó

Discret. Math., 2008

Additive approximation for bounded degree survivable network design.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Degree Bounded Matroids and Submodular Flows.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

Degree Bounded Network Design with Metric Costs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Approximating minimum bounded degree spanning trees to within one of optimal.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Survivable network design with degree or order constraints.

[BibT_eX]

[DOI]

Joseph Naor

Mohammad R. Salavatipour

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

On approximate min-max theorems for graph connectivity problems.

[BibT_eX]

[DOI]

PhD thesis, 2006

On achieving maximum multicast throughput in undirected networks.

[BibT_eX]

[DOI]

Zongpeng Li

Baochun Li

IEEE Trans. Inf. Theory, 2006

Randomly Colouring Graphs with Girth Five and Large Maximum Degree.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Michael Molloy

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping.

[BibT_eX]

[DOI]

Proceedings of the Computational Science, 2006

Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

Packing Steiner Forests.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2005

On achieving optimal throughput with network coding.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005

2004

Recognizing Powers of Proper Interval, Split, and Chordal Graph.

[BibT_eX]

[DOI]

Derek G. Corneil

SIAM J. Discret. Math., 2004

Bipartite roots of graphs.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem.

[BibT_eX]

[DOI]