Zobrazeno 1 - 10
of 38
pro vyhledávání: '"Chen, Justin Y."'
Autor:
Aamand, Anders, Andoni, Alexandr, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep, Xu, Haike
We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a ``query'' distribution $q$ over $[n]$, output $p_i$ that is ``close'
Externí odkaz:
http://arxiv.org/abs/2410.23087
Autor:
Aamand, Anders, Chen, Justin Y., Dalirrooyfard, Mina, Mitrović, Slobodan, Nevmyvaka, Yuriy, Silwal, Sandeep, Xu, Yinzhan
Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-H
Externí odkaz:
http://arxiv.org/abs/2408.01798
Recent work suggests that large language models may implicitly learn world models. How should we assess this possibility? We formalize this question for the case where the underlying reality is governed by a deterministic finite automaton. This inclu
Externí odkaz:
http://arxiv.org/abs/2406.03689
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the e
Externí odkaz:
http://arxiv.org/abs/2312.07535
Autor:
Aamand, Anders, Chen, Justin Y., Liu, Allen, Silwal, Sandeep, Sukprasert, Pattara, Vakilian, Ali, Zhang, Fred
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance of every data point to its own
Externí odkaz:
http://arxiv.org/abs/2309.16840
Autor:
Chen, Justin Y.
Streaming algorithms allow for space-efficient processing of massive datasets. The distribution of the frequencies of items in a large dataset is often used to characterize that data: e.g., the data is heavy-tailed, the data follows a power law, or t
Externí odkaz:
https://hdl.handle.net/1721.1/150228
Autor:
Aamand, Anders, Andoni, Alexandr, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep
We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$
Externí odkaz:
http://arxiv.org/abs/2306.11312
Autor:
Schiefer, Nicholas, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep, Wagner, Tal
An $\varepsilon$-approximate quantile sketch over a stream of $n$ inputs approximates the rank of any query point $q$ - that is, the number of input points less than $q$ - up to an additive error of $\varepsilon n$, generally with some probability of
Externí odkaz:
http://arxiv.org/abs/2304.07652
We give improved tradeoffs between space and regret for the online learning with expert advice problem over $T$ days with $n$ experts. Given a space budget of $n^{\delta}$ for $\delta \in (0,1)$, we provide an algorithm achieving regret $\tilde{O}(n^
Externí odkaz:
http://arxiv.org/abs/2303.01453
Autor:
Aamand, Anders, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Rubinfeld, Ronitt, Schiefer, Nicholas, Silwal, Sandeep, Wagner, Tal
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GN
Externí odkaz:
http://arxiv.org/abs/2211.03232