7 Search Results for "Liu, Allen"


Document
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-dev.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
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial

Authors: Adir Morgan, Shay Solomon, and Nicole Wein

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
We revisit the minimum dominating set problem on graphs with arboricity bounded by α. In the (standard) centralized setting, Bansal and Umboh [Bansal and Umboh, 2017] gave an O(α)-approximation LP rounding algorithm, which also translates into a near-linear time algorithm using general-purpose approximation results for explicit mixed packing and covering or pure covering LPs [Koufogiannakis and Young, 2014; Young, 2014; Allen-Zhu and Orecchia, 2019; Quanrud, 2020]. Moreover, [Bansal and Umboh, 2017] showed that it is NP-hard to achieve an asymptotic improvement for the approximation factor. On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010], and Jones et al. [Jones et al., 2013], achieve an approximation factor of O(α²) in linear time. There is a similar situation in the distributed setting: While there is an O(log² n)-round LP-based O(α)-approximation algorithm implied in [Kuhn et al., 2006], the best non-LP-based algorithm by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010] is an implementation of their centralized algorithm, providing an O(α²)-approximation within O(log n) rounds. We address the questions of whether one can achieve an O(α)-approximation algorithm that is elementary, i.e., not based on any LP-based methods, either in the centralized setting or in the distributed setting. We resolve both questions in the affirmative, and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms. Our contribution is two-fold: 1) In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time: an O(α)-approximation in linear time. The previous state-of-the-art O(α)-approximation algorithms are (1) LP-based, (2) more complicated, and (3) have super-linear running time. 2) Based on our centralized algorithm, we design a distributed combinatorial O(α)-approximation algorithm in the CONGEST model that runs in O(αlog n) rounds with high probability. Not only does this result provide the first nontrivial non-LP-based distributed o(α²)-approximation algorithm for this problem, it also outperforms the best LP-based distributed algorithm for a wide range of parameters.

Cite as

Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{morgan_et_al:LIPIcs.DISC.2021.33,
  author =	{Morgan, Adir and Solomon, Shay and Wein, Nicole},
  title =	{{Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.33},
  URN =		{urn:nbn:de:0030-drops-148353},
  doi =		{10.4230/LIPIcs.DISC.2021.33},
  annote =	{Keywords: Graph Algorithms, Dominating Set, Bounded Arboricity, Linear time algorithms}
}
Document
Matrix Rigidity Depends on the Target Field

Authors: László Babai and Bohdan Kivva

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.

Cite as

László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.CCC.2021.41,
  author =	{Babai, L\'{a}szl\'{o} and Kivva, Bohdan},
  title =	{{Matrix Rigidity Depends on the Target Field}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{41:1--41:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.41},
  URN =		{urn:nbn:de:0030-drops-143153},
  doi =		{10.4230/LIPIcs.CCC.2021.41},
  annote =	{Keywords: Matrix rigidity, field extension}
}
Document
Distributed Load Balancing: A New Framework and Improved Guarantees

Authors: Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam

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


Abstract
Inspired by applications on search engines and web servers, we consider a load balancing problem with a general convex objective function. In this problem, we are given a bipartite graph on a set of sources S and a set of workers W and the goal is to distribute the load from each source among its neighboring workers such that the total load of workers are as balanced as possible. We present a new distributed algorithm that works with any symmetric non-decreasing convex function for evaluating the balancedness of the workers' load. Our algorithm computes a nearly optimal allocation of loads in O(log n log² d/ε³) rounds where n is the number of nodes, d is the maximum degree, and ε is the desired precision. If the objective is to minimize the maximum load, we modify the algorithm to obtain a nearly optimal solution in O(log n log d/ε²) rounds. This improves a line of algorithms that require a polynomial number of rounds in n and d and appear to encounter a fundamental barrier that prevents them from obtaining poly-logarithmic runtime [Berenbrink et al., 2005; Berenbrink et al., 2009; Subramanian and Scherson, 1994; Rabani et al., 1998]. In our paper, we introduce a novel primal-dual approach with multiplicative weight updates that allows us to circumvent this barrier. Our algorithm is inspired by [Agrawal et al., 2018] and other distributed algorithms for optimizing linear objectives but introduces several new twists to deal with general convex objectives.

Cite as

Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed Load Balancing: A New Framework and Improved Guarantees. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.ITCS.2021.79,
  author =	{Ahmadian, Sara and Liu, Allen and Peng, Binghui and Zadimoghaddam, Morteza},
  title =	{{Distributed Load Balancing: A New Framework and Improved Guarantees}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{79:1--79: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.79},
  URN =		{urn:nbn:de:0030-drops-136186},
  doi =		{10.4230/LIPIcs.ITCS.2021.79},
  annote =	{Keywords: Load balancing, Distributed algorithms}
}
Document
Algorithms and Adaptivity Gaps for Stochastic k-TSP

Authors: Haotian Jiang, Jian Li, Daogao Liu, and Sahil Singla

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
Given a metric (V,d) and a root ∈ V, the classic k-TSP problem is to find a tour originating at the root of minimum length that visits at least k nodes in V. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochastic versions of k-TSP. In Stoch-Reward k-TSP, originally defined by Ene-Nagarajan-Saket [Ene et al., 2018], each vertex v in the given metric (V,d) contains a stochastic reward R_v. The goal is to adaptively find a tour of minimum expected length that collects at least reward k; here "adaptively" means our next decision may depend on previous outcomes. Ene et al. give an O(log k)-approximation adaptive algorithm for this problem, and left open if there is an O(1)-approximation algorithm. We totally resolve their open question, and even give an O(1)-approximation non-adaptive algorithm for Stoch-Reward k-TSP. We also introduce and obtain similar results for the Stoch-Cost k-TSP problem. In this problem each vertex v has a stochastic cost C_v, and the goal is to visit and select at least k vertices to minimize the expected sum of tour length and cost of selected vertices. Besides being a natural stochastic generalization of k-TSP, this problem is also interesting because it generalizes the Price of Information framework [Singla, 2018] from deterministic probing costs to metric probing costs. Our techniques are based on two crucial ideas: "repetitions" and "critical scaling". In general, replacing a random variable with its expectation leads to very poor results. We show that for our problems, if we truncate the random variables at an ideal threshold, then their expected values form a good surrogate. Here, we rely on running several repetitions of our algorithm with the same threshold, and then argue concentration using Freedman’s and Jogdeo-Samuels' inequalities. Unfortunately, this ideal threshold depends on how far we are from achieving our target k, which a non-adaptive algorithm does not know. To overcome this barrier, we truncate the random variables at various different scales and identify a "critical" scale.

Cite as

Haotian Jiang, Jian Li, Daogao Liu, and Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic k-TSP. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 45:1-45:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ITCS.2020.45,
  author =	{Jiang, Haotian and Li, Jian and Liu, Daogao and Singla, Sahil},
  title =	{{Algorithms and Adaptivity Gaps for Stochastic k-TSP}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{45:1--45:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.45},
  URN =		{urn:nbn:de:0030-drops-117308},
  doi =		{10.4230/LIPIcs.ITCS.2020.45},
  annote =	{Keywords: approximation algorithms, stochastic optimization, travelling salesman problem}
}
Document
Jointly Embedding Multiple Single-Cell Omics Measurements

Authors: Jie Liu, Yuanhao Huang, Ritambhara Singh, Jean-Philippe Vert, and William Stafford Noble

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)


Abstract
Many single-cell sequencing technologies are now available, but it is still difficult to apply multiple sequencing technologies to the same single cell. In this paper, we propose an unsupervised manifold alignment algorithm, MMD-MA, for integrating multiple measurements carried out on disjoint aliquots of a given population of cells. Effectively, MMD-MA performs an in silico co-assay by embedding cells measured in different ways into a learned latent space. In the MMD-MA algorithm, single-cell data points from multiple domains are aligned by optimizing an objective function with three components: (1) a maximum mean discrepancy (MMD) term to encourage the differently measured points to have similar distributions in the latent space, (2) a distortion term to preserve the structure of the data between the input space and the latent space, and (3) a penalty term to avoid collapse to a trivial solution. Notably, MMD-MA does not require any correspondence information across data modalities, either between the cells or between the features. Furthermore, MMD-MA’s weak distributional requirements for the domains to be aligned allow the algorithm to integrate heterogeneous types of single cell measures, such as gene expression, DNA accessibility, chromatin organization, methylation, and imaging data. We demonstrate the utility of MMD-MA in simulation experiments and using a real data set involving single-cell gene expression and methylation data.

Cite as

Jie Liu, Yuanhao Huang, Ritambhara Singh, Jean-Philippe Vert, and William Stafford Noble. Jointly Embedding Multiple Single-Cell Omics Measurements. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.WABI.2019.10,
  author =	{Liu, Jie and Huang, Yuanhao and Singh, Ritambhara and Vert, Jean-Philippe and Noble, William Stafford},
  title =	{{Jointly Embedding Multiple Single-Cell Omics Measurements}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.10},
  URN =		{urn:nbn:de:0030-drops-110401},
  doi =		{10.4230/LIPIcs.WABI.2019.10},
  annote =	{Keywords: Manifold alignment, single-cell sequencing}
}
Document
Fourier and Circulant Matrices Are Not Rigid

Authors: Zeev Dvir and Allen Liu

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
The concept of matrix rigidity was first introduced by Valiant in [Friedman, 1993]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed in [Friedman, 1993] that rigidity can be used to prove arithmetic circuit lower bounds. In a surprising result, Alman and Williams showed that the (real valued) Hadamard matrix, which was conjectured to be rigid, is actually not very rigid. This line of work was extended by [Dvir and Edelman, 2017] to a family of matrices related to the Hadamard matrix, but over finite fields. In our work, we take another step in this direction and show that for any abelian group G and function f:G - > {C}, the matrix given by M_{xy} = f(x - y) for x,y in G is not rigid. In particular, we get that complex valued Fourier matrices, circulant matrices, and Toeplitz matrices are all not rigid and cannot be used to carry out Valiant’s approach to proving circuit lower bounds. This complements a recent result of Goldreich and Tal [Goldreich and Tal, 2016] who showed that Toeplitz matrices are nontrivially rigid (but not enough for Valiant’s method). Our work differs from previous non-rigidity results in that those works considered matrices whose underlying group of symmetries was of the form {F}_p^n with p fixed and n tending to infinity, while in the families of matrices we study, the underlying group of symmetries can be any abelian group and, in particular, the cyclic group {Z}_N, which has very different structure. Our results also suggest natural new candidates for rigidity in the form of matrices whose symmetry groups are highly non-abelian. Our proof has four parts. The first extends the results of [Josh Alman and Ryan Williams, 2016; Dvir and Edelman, 2017] to generalized Hadamard matrices over the complex numbers via a new proof technique. The second part handles the N x N Fourier matrix when N has a particularly nice factorization that allows us to embed smaller copies of (generalized) Hadamard matrices inside of it. The third part uses results from number theory to bootstrap the non-rigidity for these special values of N and extend to all sufficiently large N. The fourth and final part involves using the non-rigidity of the Fourier matrix to show that the group algebra matrix, given by M_{xy} = f(x - y) for x,y in G, is not rigid for any function f and abelian group G.

Cite as

Zeev Dvir and Allen Liu. Fourier and Circulant Matrices Are Not Rigid. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.CCC.2019.17,
  author =	{Dvir, Zeev and Liu, Allen},
  title =	{{Fourier and Circulant Matrices Are Not Rigid}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{17:1--17:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.17},
  URN =		{urn:nbn:de:0030-drops-108390},
  doi =		{10.4230/LIPIcs.CCC.2019.17},
  annote =	{Keywords: Rigidity, Fourier matrix, Circulant matrix}
}
  • Refine by Author
  • 2 Liu, Allen
  • 1 Ahmadian, Sara
  • 1 Babai, László
  • 1 Dvir, Zeev
  • 1 Huang, Yuanhao
  • Show More...

  • Refine by Classification
  • 2 Theory of computation
  • 2 Theory of computation → Distributed algorithms
  • 1 Applied computing → Computational biology
  • 1 Computing methodologies → Dimensionality reduction and manifold learning
  • 1 Computing methodologies → Machine learning algorithms
  • Show More...

  • Refine by Keyword
  • 1 Bounded Arboricity
  • 1 Circulant matrix
  • 1 Discrepancy
  • 1 Distributed algorithms
  • 1 Dominating Set
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2021
  • 2 2019
  • 1 2020
  • 1 2022

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