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
∙
05/31/2023
Active causal structure learning with advice
We introduce the problem of active causal structure learning with advice...
research
∙
04/13/2023
Near-Optimal Degree Testing for Bayes Nets
This paper considers the problem of testing the maximum in-degree of the...
research
∙
02/24/2023
Constraint Optimization over Semirings
Interpretations of logical formulas over semirings have applications in ...
research
∙
02/10/2023
On the Interventional Kullback-Leibler Divergence
Modern machine learning approaches excel in static settings where a larg...
research
∙
01/01/2023
An Adaptive Kernel Approach to Federated Learning of Heterogeneous Causal Effects
We propose a new causal inference framework to learn causal effects from...
research
∙
06/30/2022
Verification and search algorithms for causal DAGs
We study two problems related to recovering causal graphs from intervent...
research
∙
06/14/2022
On Approximating Total Variation Distance
Total variation distance (TV distance) is a fundamental notion of distan...
research
∙
04/19/2022
Independence Testing for Bounded Degree Bayesian Network
We study the following independence testing problem: given access to sam...
research
∙
04/18/2022
Low Degree Testing over the Reals
We study the problem of testing whether a function f: ℝ^n →ℝ is a polyno...
research
∙
02/22/2022
Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals
A universal 1-bit compressive sensing (CS) scheme consists of a measurem...
research
∙
07/25/2021
Efficient inference of interventional distributions
We consider the problem of efficiently inferring interventional distribu...
research
∙
07/22/2021
Learning Sparse Fixed-Structure Gaussian Bayesian Networks
Gaussian Bayesian networks (a.k.a. linear Gaussian structural equation m...
research
∙
06/17/2021
Identifiability of AMP chain graph models
We study identifiability of Andersson-Madigan-Perlman (AMP) chain graph ...
research
∙
05/03/2021
Model Counting meets F0 Estimation
Constraint satisfaction problems (CSP's) and data stream models are two ...
research
∙
12/29/2020
Testing Product Distributions: A Closer Look
We study the problems of identity and closeness testing of n-dimensional...
research
∙
11/27/2020
Eco-Routing Using Open Street Maps
A vehicle's fuel consumption depends on its type, the speed, the conditi...
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
∙
06/17/2020
Efficient Statistics for Sparse Graphical Models from Truncated Samples
In this paper, we study high-dimensional estimation from truncated sampl...
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
Efficiently Learning and Sampling Interventional Distributions from Observations
We study the problem of efficiently estimating the effect of an interven...
research
∙
11/25/2019
Combinatorial lower bounds for 3-query LDCs
A code is called a q-query locally decodable code (LDC) if there is a ra...
research
∙
09/04/2019
Parameterized Intractability of Even Set and Shortest Vector Problem
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
05/28/2019
Average Bias and Polynomial Sources
We identify a new notion of pseudorandomness for randomness sources, whi...
research
∙
05/24/2018
Learning and Testing Causal Models with Interventions
We consider testing and learning problems on causal Bayesian networks as...
research
∙
03/26/2018
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
07/06/2017
Hardness of learning noisy halfspaces using polynomial thresholds
We prove the hardness of weakly learning halfspaces in the presence of a...
research
∙
08/19/2015