research
∙
09/17/2023
Total Variation Distance Estimation Is as Easy as Probabilistic Inference
In this paper, we establish a novel connection between total variation (...
share
research
∙
04/10/2023
Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma
A partition 𝒫 of ℝ^d is called a (k,ε)-secluded partition if, for every ...
research
∙
04/05/2023
List and Certificate Complexities in Replicable Learning
We investigate replicable learning algorithms. Ideally, we would like to...
research
∙
02/24/2023
Constraint Optimization over Semirings
Interpretations of logical formulas over semirings have applications in ...
research
∙
01/24/2023
Distinct Elements in Streams: An Algorithm for the (Text) Book
Given a data stream 𝒟 = ⟨ a_1, a_2, …, a_m ⟩ of m elements where each a_...
research
∙
11/04/2022
Geometry of Rounding
Rounding has proven to be a fundamental tool in theoretical computer sci...
research
∙
06/14/2022
On Approximating Total Variation Distance
Total variation distance (TV distance) is a fundamental notion of distan...
research
∙
07/25/2021
Efficient inference of interventional distributions
We consider the problem of efficiently inferring interventional distribu...
research
∙
05/03/2021
Model Counting meets F0 Estimation
Constraint satisfaction problems (CSP's) and data stream models are two ...
research
∙
03/15/2021
Promise Problems Meet Pseudodeterminism
The Acceptance Probability Estimation Problem (APEP) is to additively ap...
research
∙
12/29/2020
Testing Product Distributions: A Closer Look
We study the problems of identity and closeness testing of n-dimensional...
research
∙
11/09/2020
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
We provide finite sample guarantees for the classical Chow-Liu algorithm...
research
∙
02/13/2020
Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
We design efficient distance approximation algorithms for several classe...
research
∙
02/11/2020