2 Search Results for "Li, Angsheng"

Document

DOI: 10.4230/LIPIcs.STACS.2015.622

Testing Small Set Expansion in General Graphs

Authors: Angsheng Li and Pan Peng

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We consider the problem of testing small set expansion for general graphs. A graph G is a (k,\phi)-expander if every subset of volume at most k has conductance at least \phi. Small set expansion has recently received significant attention due to its close connection to the unique games conjecture, the local graph partitioning algorithms and locally testable codes. We give testers with two-sided error and one-sided error in the \adjacency list model that allows degree and neighbor queries to the oracle of the input graph. The testers take as input an n-vertex graph G, a volume bound k, an expansion bound \phi and a distance parameter \varepsilon>0. For the two-sided error tester, with probability at least 2/3, it accepts the graph if it is a (k,\phi)-expander and rejects the graph if it is \varepsilon-far from any (k^*,\phi^*)-expander, where k^*=\Theta(k\varepsilon) and \phi^*=\Theta(\frac{\phi^4}{\min\{\log(4m/k),\log n\}\cdot(\ln k)}). The query complexity and running time of the tester are \widetilde{O}(\sqrt{m}\phi^{-4}\varepsilon^{-2}), where m is the number of edges of the graph. For the one-sided error tester, it accepts every (k,\phi)-expander, and with probability at least 2/3, rejects every graph that is \varepsilon-far from (k^*,\phi^*)-expander, where k^*=O(k^{1-\xi}) and \phi^*=O(\xi\phi^2) for any 0<\xi<1. The query complexity and running time of this tester are \widetilde{O}(\sqrt{\frac{n}{\varepsilon^3}}+\frac{k}{\varepsilon \phi^4}). We also give a two-sided error tester in the \textit{rotation map} model that allows \textit{(neighbor, index)} queries and degree queries. This tester has asymptotically almost the same query complexity and running time as the two-sided error tester in the adjacency list model, but has a better performance: it can distinguish any $(k,\phi)$-expander from graphs that are $\varepsilon$-far from $(k^*,\phi^*)$-expanders, where $k^*=\Theta(k\varepsilon)$ and $\phi^*=\Theta(\frac{\phi^2}{\min\{\log(4m/k),\log n\}\cdot(\ln k)})$. In our analysis, we introduce a new graph product called \textit{non-uniform replacement product} that transforms a general graph into a bounded degree graph, and approximately preserves the expansion profile as well as the corresponding spectral property.

Cite as

Angsheng Li and Pan Peng. Testing Small Set Expansion in General Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 622-635, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2015.622,
  author =	{Li, Angsheng and Peng, Pan},
  title =	{{Testing Small Set Expansion in General Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{622--635},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.622},
  URN =		{urn:nbn:de:0030-drops-49461},
  doi =		{10.4230/LIPIcs.STACS.2015.622},
  annote =	{Keywords: graph property testing, small set expansion, random walks, spectral graph theory}
}

Document

Extended Abstract

DOI: 10.4230/LIPIcs.STACS.2008.1368

A Theory for Valiant's Matchcircuits (Extended Abstract)

Authors: Angsheng Li and Mingji Xia

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every $k$, the nonsingular character matrices of $k$-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).

Cite as

Angsheng Li and Mingji Xia. A Theory for Valiant's Matchcircuits (Extended Abstract). In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 491-502, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2008.1368,
  author =	{Li, Angsheng and Xia, Mingji},
  title =	{{A Theory for Valiant's Matchcircuits}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{491--502},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1368},
  URN =		{urn:nbn:de:0030-drops-13686},
  doi =		{10.4230/LIPIcs.STACS.2008.1368},
  annote =	{Keywords: Pfaffian, Matchgate, Matchcircuit}
}

Refine by Author
2 Li, Angsheng
1 Peng, Pan
1 Xia, Mingji

Refine by Classification

Refine by Keyword
1 Matchcircuit
1 Matchgate
1 Pfaffian
1 graph property testing
1 random walks
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2008
1 2015

2 Search Results for "Li, Angsheng"

Testing Small Set Expansion in General Graphs

Abstract

Cite as

A Theory for Valiant's Matchcircuits (Extended Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message