35 citations · 82 across the 23 of their papers we have counts for
29 papers
Mean Testing under Truncation beyond Gaussian
Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis
We characterize the fundamental limits of high-dimensional mean testing under arbitrary truncation, where samples are drawn from the conditional distribution for…
Product distribution learning with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
Given i.i.d.~samples from an unknown distribution , the goal of distribution learning is to recover the parameters of a distribution that is close to . When belongs to th…
Learning High-dimensional Gaussians from Censored Data
Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis +1
We provide efficient algorithms for the problem of distribution learning from high-dimensional Gaussian data where in each sample, some of the variable values are missing. We suppo…
Gaussian Mean Testing under Truncation
Clément L. Canonne, Themis Gouleakis, Yuhao Wang +1
We consider the task of Gaussian mean testing, that is, of testing whether a high-dimensional vector perturbed by white noise has large magnitude, or is the zero vector. This quest…
Learning multivariate Gaussians with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is…
Online bipartite matching with imperfect advice
Davin Choo, Themis Gouleakis, Chun Kai Ling +1
We study the problem of online unweighted bipartite matching with offline vertices and online vertices where one wishes to be competitive against the optimal offline algori…
Active causal structure learning with advice
Davin Choo, Themis Gouleakis, Arnab Bhattacharyya
We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observati…
Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost) Everywhere Else
Evripidis Bampis, Bruno Escoffier, Themis Gouleakis +4
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric sp…
Learning-Augmented Algorithms for Online TSP on the Line
Themis Gouleakis, Konstantinos Lakis, Golnoosh Shahkarami
We study the online Traveling Salesman Problem (TSP) on the line augmented with machine-learned predictions. In the classical problem, there is a stream of requests released over t…
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler +2
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (a…
Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
Ioannis Anagnostides, Themis Gouleakis
The $\hybrid$ model was recently introduced by Augustine et al. \cite{DBLP:conf/soda/AugustineHKSS20} in order to characterize from an algorithmic standpoint the capabilities of ne…
Improved Bounds for Online Facility Location with Predictions
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis +2
We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and mu…
Computationally and Statistically Efficient Truncated Regression
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos +1
We provide a computationally and statistically efficient estimator for the classical problem of truncated linear regression, where the dependent variable and its co…
Robust Learning under Strong Noise via SQs
Ioannis Anagnostides, Themis Gouleakis, Ali Marashian
This work provides several new insights on the robustness of Kearns' statistical query framework against challenging label-noise models. First, we build on a recent result by \cite…
Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane +2
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property…
Secretary and Online Matching Problems with Machine Learned Advice
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer +1
The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an iss…
Towards Testing Monotonicity of Distributions Over General Posets
Maryam Aliakbarpour, Themis Gouleakis, John Peebles +2
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution over a poset is monotone if, for any…
Communication and Memory Efficient Testing of Discrete Distributions
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane +1
We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize…
Distribution-Independent PAC Learning of Halfspaces with Massart Noise
Ilias Diakonikolas, Themis Gouleakis, Christos Tzamos
We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples $(\mathbf{x…
Simple Local Computation Algorithms for the General Lovasz Local Lemma
Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos
We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lovász Local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld…
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…
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad +2
We present -round algorithms in the Massively Parallel Computation (MPC) model, with memory per machine, that compute a maximal independent set, a $1+…
Certified Computation from Unreliable Datasets
Themis Gouleakis, Christos Tzamos, Manolis Zampetakis
A wide range of learning tasks require human input in labeling massive data. The collected data though are usually low quality and contain inaccuracies and errors. As a result, mod…
Optimal Identity Testing with High Probability
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution ove…