Zobrazeno 1 - 10
of 93
pro vyhledávání: '"Vinodchandran, N. V."'
We present two new approaches for point prediction with streaming data. One is based on the Count-Min sketch (CMS) and the other is based on Gaussian process priors with a random bias. These methods are intended for the most general predictive proble
Externí odkaz:
http://arxiv.org/abs/2408.01318
Autor:
Bhattacharyya, Arnab, Gayen, Sutanu, John, Philips George, Sen, Sayantan, Vinodchandran, N. V.
This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the expone
Externí odkaz:
http://arxiv.org/abs/2405.07914
Autor:
Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S., Myrisiotis, Dimitrios, Pavan, A., Vinodchandran, N. V.
We show that computing the total variation distance between two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the mar
Externí odkaz:
http://arxiv.org/abs/2405.08255
Autor:
Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S., Myrisiotis, Dimitrios, Pavan, A., Vinodchandran, N. V.
In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabil
Externí odkaz:
http://arxiv.org/abs/2309.09134
We establish a "neighborhood" variant of the cubical KKM lemma and the Lebesgue covering theorem and deduce a discretized version which is a "neighborhood" variant of Sperner's lemma on the cube. The main result is the following: for any coloring of
Externí odkaz:
http://arxiv.org/abs/2306.12593
A partition $\mathcal{P}$ of $\mathbb{R}^d$ is called a $(k,\varepsilon)$-secluded partition if, for every $\vec{p} \in \mathbb{R}^d$, the ball $\overline{B}_{\infty}(\varepsilon, \vec{p})$ intersects at most $k$ members of $\mathcal{P}$. A goal in d
Externí odkaz:
http://arxiv.org/abs/2304.04837
We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe a different set of samples from the unknown data distribution. In gen
Externí odkaz:
http://arxiv.org/abs/2304.02240
Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Exampl
Externí odkaz:
http://arxiv.org/abs/2302.12937
Publikováno v:
Apppeared in Proceedings of 30th Annual European Symposium on Algorithms (ESA 2022)
Given a data stream $\mathcal{A} = \langle a_1, a_2, \ldots, a_m \rangle$ of $m$ elements where each $a_i \in [n]$, the Distinct Elements problem is to estimate the number of distinct elements in $\mathcal{A}$.Distinct Elements has been a subject of
Externí odkaz:
http://arxiv.org/abs/2301.10191
Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the {\em secluded hypercube
Externí odkaz:
http://arxiv.org/abs/2211.02694