Arrow Research search

Author name cluster

Lap Chi Lau

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
1 author row

Possible papers

23

STOC Conference 2023 Conference Paper

Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues

  • Lap Chi Lau
  • Kam Chuen Tung
  • Robert Wang 0004

We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. The goal is to develop a new spectral theory for directed graphs and an alternative spectral theory for hypergraphs. The first main result is a Cheeger inequality relating the vertex expansion of a directed graph to the vertex-capacitated maximum reweighted second eigenvalue. This provides a combinatorial characterization of the fastest mixing time of a directed graph by vertex expansion, and builds a new connection between reweighted eigenvalued, vertex expansion, and fastest mixing time for directed graphs. The second main result is a stronger Cheeger inequality relating the edge conductance of a directed graph to the edge-capacitated maximum reweighted second eigenvalue. This provides a certificate for a directed graph to be an expander and a spectral algorithm to find a sparse cut in a directed graph, playing a similar role as Cheeger's inequality in certifying graph expansion and in the spectral partitioning algorithm for undirected graphs. We also use this reweighted eigenvalue approach to derive the improved Cheeger inequality for directed graphs, and furthermore to derive several Cheeger inequalities for hypergraphs that match and improve the existing results. These are supporting results that this provides a unifying approach to lift the spectral theory for undirected graphs to more general settings.

Details

FOCS Conference 2022 Conference Paper

Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

  • Tsz Chiu Kwok
  • Lap Chi Lau
  • Kam Chuen Tung

The classical Cheeger’s inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality connecting the vertex expansion of a graph and the maximum reweighted second smallest eigenvalue of the Laplacian matrix. In this work, we first improve their result to a logarithmic dependence on the maximum degree in the graph, which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include an analog of Trevisan’s result on bipartiteness, an analog of higher order Cheeger’s inequality, and an analog of improved Cheeger’s inequality. Finally, inspired by this connection, we present negative evidence to the 0/1-polytope edge expansion conjecture by Mihail and Vazirani. We construct 0/1-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these 0/1-polytopes is almost linear in the graph size.

Details

SODA Conference 2021 Conference Paper

A Local Search Framework for Experimental Design

  • Lap Chi Lau
  • Hong Zhou 0001

We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for experimental design problems. This framework provides a unifying approach to match and improve all known results in D/A/E-design and to obtain new results in previously unknown settings. • For combinatorial algorithms, we provide a new analysis of the classical Fedorov's exchange method. We prove that this simple local search algorithm works well as long as there exists an almost optimal solution with good condition number. Moreover, we design a new combinatorial local search algorithm for E-design using the regret minimization framework. • For rounding algorithms, we provide a unified randomized exchange algorithm to match and improve previous results for D/A/E-design. Furthermore, the algorithm works in the more general setting to approximately satisfy multiple knapsack constraints, which can be used for weighted experimental design and for incorporating fairness constraints into experimental design.

Details

STOC Conference 2020 Conference Paper

Improved analysis of higher order random walks and applications

  • Vedat Levi Alev
  • Lap Chi Lau

The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. We show some applications of this result in analyzing mixing times of Markov chains, including sampling independent sets of a graph and sampling common independent sets of two partition matroids.

Details

FOCS Conference 2019 Conference Paper

Spectral Analysis of Matrix Scaling and Operator Scaling

  • Tsz Chiu Kwok
  • Lap Chi Lau
  • Akshay Ramachandran

We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear convergence. This implies that a simple gradient descent algorithm also has linear convergence under the same assumption. The spectral gap condition for operator scaling is closely related to the notion of quantum expander studied in quantum information theory. The spectral analysis also provides bounds on some important quantities of the scaling problems, such as the condition number of the scaling solution and the capacity of the matrix and operator. These results can be used in various applications of scaling problems, including matrix scaling on expander graphs, permanent lower bounds on random matrices, the Paulsen problem on random frames, and Brascamp-Lieb constants on random operators. In some applications, the inputs of interest satisfy the spectral condition and we prove significantly stronger bounds than the worst case bounds.

Details

STOC Conference 2018 Conference Paper

The Paulsen problem, continuous operator scaling, and smoothed analysis

  • Tsz Chiu Kwok
  • Lap Chi Lau
  • Yin Tat Lee
  • Akshay Ramachandran

The Paulsen problem is a basic open problem in operator theory: Given vectors u 1 , …, u n ∈ ℝ d that are є-nearly satisfying the Parseval’s condition and the equal norm condition, is it close to a set of vectors v 1 , …, v n ∈ ℝ d that exactly satisfy the Parseval’s condition and the equal norm condition? Given u 1 , …, u n , the squared distance (to the set of exact solutions) is defined as inf v ∑ i =1 n || u i − v i || 2 2 where the infimum is over the set of exact solutions. Previous results show that the squared distance of any є-nearly solution is at most O ( poly ( d , n ,є)) and there are є-nearly solutions with squared distance at least Ω( d є). The fundamental open question is whether the squared distance can be independent of the number of vectors n . We answer this question affirmatively by proving that the squared distance of any є-nearly solution is O ( d 13/2 є). Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any є-nearly solution is O ( d 2 n є). Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an є-nearly solution is O ( d 5/2 є) when n is large enough and є is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyzing the operator scaling algorithm.

Details

STOC Conference 2013 Conference Paper

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

  • Tsz Chiu Kwok
  • Lap Chi Lau
  • Yin Tat Lee
  • Shayan Oveis Gharan
  • Luca Trevisan 0001

Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ 1 ≤ λ 2 ≤ ... ≤ λ n ≤ 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k ≥ 2, [φ(G) = O(k) l 2 /√l k ,] and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any $k$. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if l k is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.

Details

STOC Conference 2012 Conference Paper

Fast matrix rank algorithms and applications

  • Ho Yee Cheung
  • Tsz Chiu Kwok
  • Lap Chi Lau

We consider the problem of computing the rank of an mxn matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in O(|A| + r w ) field operations, where |A| denotes the number of nonzero entries in A and w < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with running time O(mnr w ). Our algorithm is faster when r < max{m,n}, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in O(mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in numerical linear algebra, combinatorial optimization and dynamic data structure.

Details

FOCS Conference 2011 Conference Paper

Graph Connectivities, Network Coding, and Expander Graphs

  • Ho Yee Cheung
  • Lap Chi Lau
  • Kai Man Leung

We present a new algebraic formulation to compute edge connectivities in a directed graph, using the ideas developed in network coding. This reduces the problem of computing edge connectivities to solving systems of linear equations, thus allowing us to use tools in linear algebra to design new algorithms. Using the algebraic formulation we obtain faster algorithms for computing single source edge connectivities and all pairs edge connectivities, in some settings the amortized time to compute the edge connectivity for one pair is sub linear. Through this connection, we have also found an interesting use of expanders and super concentrators to design fast algorithms for some graph connectivity problems.

Details

STOC Conference 2008 Conference Paper

Additive approximation for bounded degree survivable network design

  • Lap Chi Lau
  • Mohit Singh

We study a general network design problem with additional degree constraints. Given connectivity requirements r uv for all pairs of vertices, a Steiner network is a graph in which there are at least r uv edge-disjoint paths between u and v for all pairs of vertices u,v . In the MINIMUM BOUNDED-DEGREE STEINER NETWORK problem, we are given an undirected graph G with an edge cost for each edge, a connectivity requirement r uv for each pair of vertices u and v , and a degree upper bound for each vertex v . The task is to find a minimum cost Steiner network which satisfies all the degree upper bounds. The aim of this paper is to design approximation algorithms that minimize the total cost and the degree violation simultaneously. Our main results are the following: There is a polynomial time algorithm which returns a Steiner forest of cost at most 2 OPT and the degree violation at each vertex is at most 3,where OPT is the cost of an optimal solution which satisfies all the degree bounds. There is a polynomial time algorithm which returns a Steiner network of cost at most 2 OPT and the degree violation at each vertex is at most 6 r max +3,where OPT is the cost of an optimal solution which satisfies all the degree bounds, and r max := max u,v { r uv }. These results achieve the best known guarantees for both the total cost and the degree violation simultaneously. As corollaries, these results provide the first additive approximation algorithms for finding low degree subgraphs including Steiner forests, k -edge-connected subgraphs, and Steiner networks. The algorithms develop on the iterative relaxation method applied to a natural linear programming relaxation as in [10, 16, 22]. The new algorithms avoid paying a multiplicative factor of two on the degree bounds even though the algorithm can only pick edges with fractional value 1/2 . This is based on a stronger characterization of the basic so-algorithm is nearly tight.

Details

FOCS Conference 2008 Conference Paper

Degree Bounded Network Design with Metric Costs

  • Yuk Hei Chan
  • Wai Shing Fung
  • Lap Chi Lau
  • Chun Kong Yung

Given a complete undirected graph, a cost function on edges and a degree bound B, the degree bounded network design problem is to find a minimum cost simple subgraph with maximum degree B satisfying given connectivity requirements. Even for simple connectivity requirement such as finding a spanning tree, computing a feasible solution for the degree bounded network design problem is already NP-hard, and thus there is no polynomial factor approximation algorithm for this problem. In this paper, we show that when the cost function satisfies triangle inequalities, there are constant factor approximation algorithms for various degree bounded network design problems. Global edge-connectivity: There is a (2+1/k)-approximation algorithm for the minimum bounded degree k-edge-connected subgraph problem. Local edge-connectivity: There is a 6-approximation algorithm for the minimum bounded degree Steiner network problem. Global vertex-connectivity: there is a (2+(k-1)/n+1/k)-approximation algorithm for the minimum bounded degree k-vertex-connected subgraph problem. Spanning tree: there is an (1+1/(d-1))-approximation algorithm for the minimum bounded degree spanning tree problem. These approximation algorithms return solutions with smallest possible maximum degree, and the cost guarantee is obtained by comparing to the optimal cost when there are no degree constraints. This demonstrates that degree constraints can be incorporated into network design problems with metric costs. Our algorithms can be seen as a generalization of Christofides' algorithm for metric TSP. The main technical tool is a simplicity-preserving edge splitting-off operation, which is used to "short-cut" vertices with high degree while maintaining connectivity requirements and preserving simplicity of the solutions.

Details

STOC Conference 2007 Conference Paper

Approximating minimum bounded degree spanning trees to within one of optimal

  • Mohit Singh
  • Lap Chi Lau

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound B v on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. Let OPT be the costof an optimal solution to this problem. In this paper, we presenta polynomial time algorithm which returns a spanning tree T ofcost at most OPT and d T (v) ≤ B v +1 for all v, where d T (v) denotes the degree of v in T. This generalizes aresult of Furer and Raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v hasa degree lower bound A v and a degree upper bound B v , andreturns a spanning tree with cost at most OPT and A v - 1 ≤d T (v) ≤ B v + 1 for all v. This is essentially the bestpossible. The main technique used is an extension of the iterativerounding method introduced by Jain [12] for the design ofapproximation algorithms.

Details

FOCS Conference 2006 Conference Paper

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

  • Tamás Király
  • Lap Chi Lau

Given an undirected hypergraph and a subset of vertices S sube V with a specified root vertex r isin S, the Steiner rooted-orientation problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "connectivity" from the root r to the vertices in S is maximized. This is motivated by a multicasting problem in undirected networks as well as a generalization of some classical problems in graph theory. The main results of this paper are the following approximate min-max relations: middot Given an undirected hypergraph H, if S is 2k-hyperedge-connected in H, then H has a Steiner rooted k-hyperarc-connected orientation. middot Given an undirected graph G, if S is 2k-element-connected in G, then G has a Steiner rooted k-element-connected orientation. Both results are tight in terms of the connectivity bounds. These also give polynomial time constant factor approximation algorithms for both problems. The proofs are based on submodular techniques, and a graph decomposition technique used in the Steiner tree packing problem. Some complementary hardness results are presented at the end

Details

FOCS Conference 2004 Conference Paper

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

  • Lap Chi Lau

Given an undirected multigraph G and a subset of vertices S /spl sube/ V(G), the Steiner tree packing problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme unless P=NP). In fact, prior to this paper, not even an approximation algorithm with asymptotic ratio o(n) was known despite several attempts. In this work, we close this huge gap by presenting the first polynomial time constant factor approximation algorithm for the Steiner tree packing problem. The main theorem is an approximate min-max relation between the maximum number of edge-disjoint trees that each connects S (i. e. S-trees) and the minimum size of an edge-cut that disconnects some pair of vertices in S (i. e. S-cut). Specifically, we prove that if the minimum S-cut in G has 26k edges, then G has at least k edge-disjoint S-trees; this answers Kriesell's conjecture affirmatively up to a constant multiple. The techniques that we use are purely combinatorial, where matroid theory is the underlying ground work.

Details
v2026.09.13