Zobrazeno 1 - 10
of 16
pro vyhledávání: '"John Peebles"'
Publikováno v:
STOC
STOC '21
STOC '21
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and parameters $0< \epsilon, \delta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b041385f8b21b940a23404f875c52eee
https://escholarship.org/uc/item/3q40j4jp
https://escholarship.org/uc/item/3q40j4jp
Autor:
Salil Vadhan, John Peebles, Jack Murtagh, AmirMahdi Ahmadinejad, Jonathan A. Kelner, Aaron Sidford
Publikováno v:
FOCS
arXiv
arXiv
We provide a deterministic $\tilde{O}(\log N)$-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error ($\epsilon=1/\mathrm{poly}(N)$) whe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::880ce2b84b442a18736c9209615de131
https://doi.org/10.1109/focs46700.2020.00123
https://doi.org/10.1109/focs46700.2020.00123
Publikováno v:
Computer Vision – ECCV 2020 ISBN: 9783030585389
ECCV (6)
ECCV (6)
Existing disentanglement methods for deep generative models rely on hand-picked priors and complex encoder-based architectures. In this paper, we propose the Hessian Penalty, a simple regularization term that encourages the Hessian of a generative mo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d2f3abf26fc0e80330969a8abc4df7af
https://doi.org/10.1007/978-3-030-58539-6_35
https://doi.org/10.1007/978-3-030-58539-6_35
Publikováno v:
SIAM Journal on Computing. 49:FOCS17-350
We show that variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff's matrix-tree theorem, this is equivalent to preserving the determinant...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f3e9359f0646b94b54e4d6ce4bdbdbb5
https://doi.org/10.1137/18m1165979
https://doi.org/10.1137/18m1165979
Autor:
Jonathan A. Kelner, Michael B. Cohen, Anup Rao, Rasmus Kyng, John Peebles, Richard Peng, Aaron Sidford
Publikováno v:
arXiv
FOCS
FOCS
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an $n \times n$ Eulerian directed Laplacian with $m$ nonzero entries, we show how to compute an $\epsilon$-approximate solution in time $O(m \log^{O(1)} (
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b4f28b24ffd0cb9a9b0c95223a20624c
https://hdl.handle.net/1721.1/138046
https://hdl.handle.net/1721.1/138046
Publikováno v:
STOC
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in $\tilde{O}(n^{4/3}m^{1/2}+n^{2})$ time (The $\tilde{O}(\cdot)$ notation hides $\operatorname{polylog}(n)$ factors). The tr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b89602b4a16616500f9f74e460bef53
https://doi.org/10.1145/3055399.3055499
https://doi.org/10.1145/3055399.3055499
Autor:
Anup Rao, Jonathan A. Kelner, John Peebles, Michael B. Cohen, Adrian Vladu, Aaron Sidford, Richard Peng
Publikováno v:
arXiv
STOC
STOC
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41e1083df54b95463b11f12a0e39fc9e
https://orcid.org/0000-0002-7388-6936
https://orcid.org/0000-0002-7388-6936
Publikováno v:
FOCS
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::574ac9ef6c8aee9e27f0588313eafb53
http://arxiv.org/abs/1705.00985
http://arxiv.org/abs/1705.00985
Autor:
Maryam Aliakbarpour, Anak Yodpinyanee, Ronitt Rubinfeld, John Peebles, Amartya Shankha Biswas, Themis Gouleakis
Publikováno v:
Springer US
We study the problem of estimating the value of sums of the form S[subscript p]≜∑([x[subscript i] over p]) when one has the ability to sample x[subscript i]≥0 with probability proportional to its magnitude. When p=2 , this problem is equivalent
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e7d7118617e39cf981152adf92bf70a9
https://orcid.org/0000-0002-6514-3761
https://orcid.org/0000-0002-6514-3761
Autor:
Aaron Sidford, John Peebles, Michael B. Cohen, Jonathan A. Kelner, Adrian Vladu, Richard Peng
Publikováno v:
FOCS
arXiv
arXiv
In this paper, we provide faster algorithms for computing variousfundamental quantities associated with random walks on a directedgraph, including the stationary distribution, personalized PageRankvectors, hitting times, and escape probabilities. In
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a0f7bc7d0217625c66833f3830fa8e01