8 Search Results for "Lau, Lap Chi"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.4
Experimental Design for Any p-Norm

Authors: Lap Chi Lau, Robert Wang, and Hong Zhou

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

Abstract
We consider a general p-norm objective for experimental design problems that captures some well-studied objectives (D/A/E-design) as special cases. We prove that a randomized local search approach provides a unified algorithm to solve this problem for all nonnegative integer p. This provides the first approximation algorithm for the general p-norm objective, and a nice interpolation of the best known bounds of the special cases.
Cite as

Lap Chi Lau, Robert Wang, and Hong Zhou. Experimental Design for Any p-Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 4:1-4:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lau_et_al:LIPIcs.APPROX/RANDOM.2023.4,
  author =	{Lau, Lap Chi and Wang, Robert and Zhou, Hong},
  title =	{{Experimental Design for Any p-Norm}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.4},
  URN =		{urn:nbn:de:0030-drops-188292},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.4},
  annote =	{Keywords: Approximation Algorithm, Optimal Experimental Design, Randomized Local Search}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.49
Fine Grained Analysis of High Dimensional Random Walks

Authors: Roy Gotlib and Tali Kaufman

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

Abstract
One of the most important properties of high dimensional expanders is that high dimensional random walks converge rapidly. This property has proven to be extremely useful in a variety of fields in the theory of computer science from agreement testing to sampling, coding theory and more. In this paper we present a state of the art result in a line of works analyzing the convergence of high dimensional random walks [Tali Kaufman and David Mass, 2017; Irit Dinur and Tali Kaufman, 2017; Tali Kaufman and Izhar Oppenheim, 2018; Vedat Levi Alev and Lap Chi Lau, 2020], by presenting a structured version of the result of [Vedat Levi Alev and Lap Chi Lau, 2020]. While previous works examined the expansion in the viewpoint of the worst possible eigenvalue, in this work we relate the expansion of a function to the entire spectrum of the random walk operator using the structure of the function; We call such a theorem a Fine Grained High Order Random Walk Theorem. In sufficiently structured cases the fine grained result that we present here can be much better than the worst case while in the worst case our result is equivalent to [Vedat Levi Alev and Lap Chi Lau, 2020]. In order to prove the Fine Grained High Order Random Walk Theorem we introduce a way to bootstrap the expansion of random walks on the vertices of a complex into a fine grained understanding of higher order random walks, provided that the expansion is good enough. In addition, our single bootstrapping theorem can simultaneously yield our Fine Grained High Order Random Walk Theorem as well as the well known Trickling down Theorem. Prior to this work, High order Random walks theorems and Tricking down Theorem have been obtained from different proof methods.
Cite as

Roy Gotlib and Tali Kaufman. Fine Grained Analysis of High Dimensional Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 49:1-49:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.APPROX/RANDOM.2023.49,
  author =	{Gotlib, Roy and Kaufman, Tali},
  title =	{{Fine Grained Analysis of High Dimensional Random Walks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.49},
  URN =		{urn:nbn:de:0030-drops-188740},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.49},
  annote =	{Keywords: High Dimensional Expanders, High Dimensional Random Walks, Local Spectral Expansion, Local to Global, Trickling Down}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.18
On Testing and Robust Characterizations of Convexity

Authors: Eric Blais and Abhinav Bommireddi

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

Abstract
A body K ⊂ ℝⁿ is convex if and only if the line segment between any two points in K is completely contained within K or, equivalently, if and only if the convex hull of a set of points in K is contained within K. We show that neither of those characterizations of convexity are robust: there are bodies in ℝⁿ that are far from convex - in the sense that the volume of the symmetric difference between the set K and any convex set C is a constant fraction of the volume of K - for which a line segment between two randomly chosen points x,y ∈ K or the convex hull of a random set X of points in K is completely contained within K except with exponentially small probability. These results show that any algorithms for testing convexity based on the natural line segment and convex hull tests have exponential query complexity.
Cite as

Eric Blais and Abhinav Bommireddi. On Testing and Robust Characterizations of Convexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blais_et_al:LIPIcs.APPROX/RANDOM.2020.18,
  author =	{Blais, Eric and Bommireddi, Abhinav},
  title =	{{On Testing and Robust Characterizations of Convexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.18},
  URN =		{urn:nbn:de:0030-drops-126214},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.18},
  annote =	{Keywords: Convexity, Line segment test, Convex hull test, Intersecting cones}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.41
Graph Clustering using Effective Resistance

Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.18
Approximating Unique Games Using Low Diameter Graph Decomposition

Authors: Vedat Levi Alev and Lap Chi Lau

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

Abstract
We design approximation algorithms for Unique Gmeas when the constraint graph admits good low diameter graph decomposition. For the M2Lin(k) problem in K(r)-minor free graphs, when there is an assignment satisfying 1-eps fraction of constraints, we present an algorithm that produces an assignment satisfying 1-O(r*eps) fraction of constraints, with the approximation ratio independent of the alphabet size. A corollary is an improved approximation algorithm for the Min-UnCut problem for K(r)-minor free graphs. For general Unique Games in K(r)-minor free graphs, we provide another algorithm that produces an assignment satisfying 1-O(r *sqrt(eps)) fraction of constraints. Our approach is to round a linear programming relaxation to find a minimum subset of edges that intersects all the inconsistent cycles. We show that it is possible to apply the low diameter graph decomposition technique on the constraint graph directly, rather than to work on the label extended graph as in previous algorithms for Unique Games. The same approach applies when the constraint graph is of genus g, and we get similar results with r replaced by log g in the M2Lin(k) problem and by sqrt(log g) in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the M2Lin(k) case, and the latter result generalizes the result of Trevisan for general Unique Games.
Cite as

Vedat Levi Alev and Lap Chi Lau. Approximating Unique Games Using Low Diameter Graph Decomposition. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{levialev_et_al:LIPIcs.APPROX-RANDOM.2017.18,
  author =	{Levi Alev, Vedat and Lau, Lap Chi},
  title =	{{Approximating Unique Games Using Low Diameter Graph Decomposition}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.18},
  URN =		{urn:nbn:de:0030-drops-75676},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.18},
  annote =	{Keywords: Unique Games, Low Diameter Graph Decomposition, Bounded Genus Graphs, Fixed Minor Free Graphs, Approximation Algorithms, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.313
Lower Bounds on Expansions of Graph Powers

Authors: Tsz Chiu Kwok and Lap Chi Lau

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

Abstract
Given a lazy regular graph G, we prove that the expansion of G^t is at least sqrt(t) times the expansion of G. This bound is tight and can be generalized to small set expansion. We show some applications of this result.
Cite as

Tsz Chiu Kwok and Lap Chi Lau. Lower Bounds on Expansions of Graph Powers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 313-324, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.APPROX-RANDOM.2014.313,
  author =	{Kwok, Tsz Chiu and Lau, Lap Chi},
  title =	{{Lower Bounds on Expansions of Graph Powers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{313--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  URN =		{urn:nbn:de:0030-drops-47057},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  annote =	{Keywords: Conductance, Expansion, Graph power, Random walk}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2012.24
Iterative Methods in Combinatorial Optimization (Invited Talk)

Authors: R. Ravi

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In these lectures, I will describe a simple iterative method that supplies new proofs of integrality of linear characterizations of various basic problems in combinatorial optimization, and also allows adaptations to design approximation algorithms for NP-hard variants of these problems involving extra "degree-like" budget constraints. It is inspired by Jain's iterative rounding method for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh in their work on designing the approximation algorithm for its degree bounded version. Its application was further refined in recent work of Bansal, Khandekar and Nagarajan on degree-bounded directed network design. I will begin by reviewing the background material on LP relaxations and their solvability and properties of extreme point or vertex solutions to such problems. I will then introduce the basic framework of the method using the assignment problem, and show its application by re-deriving the approximation results of Shmoys and Tardos for the generalized assignment problem. I will then discuss linear characterizations for the spanning tree polyhedron in undirected graphs and give a new proof of integrality using an iterative method. I will then illustrate an application to approximating the degree-bounded version of the undirected problem, by proving the results of Goemans and Lau & Singh. I will continue with showing how these methods for spanning trees simplify and generalize to showing linear descriptions of maximum weight matroid bases and also maximum weight sets that are independent in two different matroids. This also leads to good additive approximation algorithms for a bounded degree version of the matroid basis problem. I will close with applications of the iterative method by revisiting Jain's original proof for the SNDP and giving a new proof that unifies its treatment with that for the Symmetric TSP polyhedron (describing joint work with Nagarajan and Singh). I will also outline the versatility of the method by pointing out the other problems for which the method has been applied, summarizing the discussion in a recent monograph I have co-authored on this topic with Lap Chi Lau and Mohit Singh (published by Cambridge University Press, 2011).
Cite as

R. Ravi. Iterative Methods in Combinatorial Optimization (Invited Talk). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, p. 24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ravi:LIPIcs.STACS.2012.24,
  author =	{Ravi, R.},
  title =	{{Iterative Methods in Combinatorial Optimization}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{24--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.24},
  URN =		{urn:nbn:de:0030-drops-33876},
  doi =		{10.4230/LIPIcs.STACS.2012.24},
  annote =	{Keywords: combinatorial optimization, linear programming, matroid}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1827
Computing Graph Roots Without Short Cycles

Authors: Babak Farzad, Lap Chi Lau, Van Bang Le, and Nguyen Ngoc Tuy

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Graph $G$ is the square of graph $H$ if two vertices $x,y$ have an edge in $G$ if and only if $x,y$ are of distance at most two in $H$. Given $H$ it is easy to compute its square $H^2$, however Motwani and Sudan proved that it is NP-complete to determine if a given graph $G$ is the square of some graph $H$ (of girth $3$). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if $G=H^2$ for some graph $H$ of small girth. The main results are the following. \begin{itemize} \item There is a graph theoretical characterization for graphs that are squares of some graph of girth at least $7$. A corollary is that if a graph $G$ has a square root $H$ of girth at least $7$ then $H$ is unique up to isomorphism. \item There is a polynomial time algorithm to recognize if $G=H^2$ for some graph $H$ of girth at least $6$. \item It is NP-complete to recognize if $G=H^2$ for some graph $H$ of girth $4$. \end{itemize} These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.
Cite as

Babak Farzad, Lap Chi Lau, Van Bang Le, and Nguyen Ngoc Tuy. Computing Graph Roots Without Short Cycles. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 397-408, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{farzad_et_al:LIPIcs.STACS.2009.1827,
  author =	{Farzad, Babak and Lau, Lap Chi and Le, Van Bang and Tuy, Nguyen Ngoc},
  title =	{{Computing Graph Roots Without Short Cycles}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{397--408},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1827},
  URN =		{urn:nbn:de:0030-drops-18279},
  doi =		{10.4230/LIPIcs.STACS.2009.1827},
  annote =	{Keywords: Graph roots, Graph powers, Recognition algorithms, NP-completeness}
}
  • Refine by Author
  • 5 Lau, Lap Chi
  • 1 Alev, Vedat Levi
  • 1 Anari, Nima
  • 1 Blais, Eric
  • 1 Bommireddi, Abhinav
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Expander graphs and randomness extractors
  • 1 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Rounding techniques
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 Conductance
  • 1 Approximation Algorithm
  • 1 Approximation Algorithms
  • 1 Bounded Genus Graphs
  • 1 Convex hull test
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2023
  • 1 2009
  • 1 2012
  • 1 2014
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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