88 citations · 311 across the 59 of their papers we have counts for
5 papers · 1 filter
Efficient Statistics, in High Dimensions, from Truncated Samples
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos +1
We provide an efficient algorithm for the classical problem, going back to Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate norm…
Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, Arturs Backurs, Christos Tzamos
Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum…
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
Gautam Kamath, Christos Tzamos
We investigate distribution testing with access to non-adaptive conditional samples. In the conditional sampling model, the algorithm is given the following access to a distributio…
Actively Avoiding Nonsense in Generative Models
Steve Hanneke, Adam Kalai, Gautam Kamath +1
A generative model may generate utter nonsense when it is fit to maximize the likelihood of observed data. This happens due to "model error," i.e., when the true data generating di…
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
Kyriakos Axiotis, Christos Tzamos
One of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset…