Christos Tzamos

research

∙ 09/20/2023

GLM Regression with Oblivious Corruptions

We demonstrate the first algorithms for the problem of regression for ge...

0 Ilias Diakonikolas, et al. ∙

research

∙ 08/06/2023

Self-Directed Linear Classification

In online classification, a learner is presented with a sequence of exam...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/06/2023

Buying Information for Stochastic Optimization

Stochastic optimization is one of the central problems in Machine Learni...

0 Mingchen Ma, et al. ∙

research

∙ 01/31/2023

Weitzman's Rule for Pandora's Box with Correlations

Pandora's Box is a central problem in decision making under uncertainty ...

0 Evangelia Gergatsouli, et al. ∙

research

∙ 12/06/2022

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

The Forster transform is a method of regularizing a dataset by placing i...

0 Ilias Diakonikolas, et al. ∙

research

∙ 11/23/2022

Perfect Sampling from Pairwise Comparisons

In this work, we study how to efficiently obtain perfect samples from a ...

0 Dimitris Fotakis, et al. ∙

research

∙ 08/22/2022

Graph Connectivity with Noisy Queries

Graph connectivity is a fundamental combinatorial optimization problem t...

0 Dimitris Fotakis, et al. ∙

research

∙ 06/17/2022

Learning a Single Neuron with Adversarial Label Noise via Gradient Descent

We study the fundamental problem of learning a single neuron, i.e., a fu...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/09/2022

Clustering with Queries under Semi-Random Noise

The seminal paper by Mazumdar and Saha <cit.> introduced an extensive li...

0 Alberto Del Pia, et al. ∙

research

∙ 05/26/2022

Contextual Pandora's Box

Pandora's Box is a fundamental stochastic optimization problem, where th...

0 Alexia Atsidakou, et al. ∙

research

∙ 04/05/2022

Buy-Many Mechanisms for Many Unit-Demand Buyers

A recent line of research has established a novel desideratum for design...

0 Shuchi Chawla, et al. ∙

research

∙ 02/10/2022

Online Learning for Min Sum Set Cover and Pandora's Box

Two central problems in Stochastic Optimization are Min Sum Set Cover an...

0 Evangelia Gergatsouli, et al. ∙

research

∙ 09/10/2021

ReLU Regression with Massart Noise

We study the fundamental problem of ReLU regression, where the goal is t...

0 Ilias Diakonikolas, et al. ∙

research

∙ 08/30/2021

Approximating Pandora's Box with Correlations

The Pandora's Box problem asks to find a search strategy over n alternat...

3 Shuchi Chawla, et al. ∙

research

∙ 08/22/2021

Efficient Algorithms for Learning from Coarse Labels

For many learning problems one may not have access to fine grained label...

0 Dimitris Fotakis, et al. ∙

research

∙ 08/19/2021

Threshold Phenomena in Learning Halfspaces with Massart Noise

We study the problem of PAC learning halfspaces on ℝ^d with Massart nois...

11 Ilias Diakonikolas, et al. ∙

research

∙ 07/12/2021

Forster Decomposition and Learning Halfspaces with Noise

A Forster transform is an operation that turns a distribution into one w...

10 Ilias Diakonikolas, et al. ∙

research

∙ 06/30/2021

A Statistical Taylor Theorem and Extrapolation of Truncated Densities

We show a statistical version of Taylor's theorem and apply this result ...

0 Constantinos Daskalakis, et al. ∙

research

∙ 06/14/2021

Boosting in the Presence of Massart Noise

We study the problem of boosting the accuracy of a weak learner in the (...

2 Ilias Diakonikolas, et al. ∙

research

∙ 06/08/2021

Pricing Ordered Items

We study the revenue guarantees and approximability of item pricing. Rec...

0 Shuchi Chawla, et al. ∙

research

∙ 02/10/2021

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

We study the problem of agnostically learning halfspaces under the Gauss...

5 Ilias Diakonikolas, et al. ∙

research

∙ 12/01/2020

Convergence and Sample Complexity of SGD in GANs

We provide theoretical convergence guarantees on training Generative Adv...

0 Vasilis Kontonis, et al. ∙

research

∙ 11/12/2020

Optimal Private Median Estimation under Minimal Distributional Assumptions

We study the fundamental task of estimating the median of an underlying ...

0 Christos Tzamos, et al. ∙

research

∙ 10/22/2020

Computationally and Statistically Efficient Truncated Regression

We provide a computationally and statistically efficient estimator for t...

0 Constantinos Daskalakis, et al. ∙

research

∙ 10/04/2020

A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise

We study the problem of PAC learning homogeneous halfspaces in the prese...

0 Ilias Diakonikolas, et al. ∙

research

∙ 08/24/2020

Fast and Simple Modular Subset Sum

We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...

0 Kyriakos Axiotis, et al. ∙

research

∙ 07/05/2020

Efficient Parameter Estimation of Truncated Boolean Product Distributions

We study the problem of estimating the parameters of a Boolean product d...

0 Dimitris Fotakis, et al. ∙

research

∙ 06/11/2020

Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

We study the problem of agnostically learning homogeneous halfspaces in ...

0 Ilias Diakonikolas, et al. ∙

research

∙ 06/11/2020

Learning Halfspaces with Tsybakov Noise

We study the efficient PAC learnability of halfspaces in the presence of...

0 Ilias Diakonikolas, et al. ∙

research

∙ 03/24/2020

Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms

We study the multi-item mechanism design problem where a monopolist sell...

0 Shuchi Chawla, et al. ∙

research

∙ 03/21/2020

Black-box Methods for Restoring Monotonicity

In many practical applications, heuristic or approximation algorithms ar...

0 Evangelia Gergatsouli, et al. ∙

research

∙ 02/13/2020

Learning Halfspaces with Massart Noise Under Structured Distributions

We study the problem of learning halfspaces with Massart noise in the di...

0 Ilias Diakonikolas, et al. ∙

research

∙ 02/10/2020

Robust Mean Estimation under Coordinate-level Corruption

Data corruption, systematic or adversarial, may skew statistical estimat...

4 Zifan Liu, et al. ∙

research

∙ 11/05/2019

Learning Optimal Search Algorithms from Data

Classical algorithm design is geared towards worst case instances and fa...

0 Shuchi Chawla, et al. ∙

research

∙ 08/02/2019

Efficient Truncated Statistics with Unknown Truncation

We study the problem of estimating the parameters of a Gaussian distribu...

0 Vasilis Kontonis, et al. ∙

research

∙ 06/26/2019

The Complexity of Black-Box Mechanism Design with Priors

We study black-box reductions from mechanism design to algorithm design ...

0 Evangelia Gergatsouli, et al. ∙

research

∙ 06/24/2019

Distribution-Independent PAC Learning of Halfspaces with Massart Noise

We study the problem of distribution-independent PAC learning of halfsp...

0 Ilias Diakonikolas, et al. ∙

research

∙ 05/13/2019

Diversity and Exploration in Social Learning

In consumer search, there is a set of items. An agent has a prior over h...

0 Nicole Immorlica, et al. ∙

research

∙ 04/26/2019

Learning to Prune: Speeding up Repeated Computations

It is common to encounter situations where one must solve a sequence of ...

12 Daniel Alabi, et al. ∙

research

∙ 02/27/2019

Buy-many mechanisms are not much better than item pricing

Multi-item mechanisms can be very complex offering many different bundle...

0 Shuchi Chawla, et al. ∙

research

∙ 02/27/2019

Reasonable multi-item mechanisms are not much better than item pricing

Multi-item mechanisms can be very complex offering many different bundle...

0 Shuchi Chawla, et al. ∙

research

∙ 09/11/2018

Efficient Statistics, in High Dimensions, from Truncated Samples

We provide an efficient algorithm for the classical problem, going back ...

0 Constantinos Daskalakis, et al. ∙

research

∙ 07/17/2018

Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

We investigate distribution testing with access to non-adaptive conditio...

0 Gautam Kamath, et al. ∙

research

∙ 07/12/2018

Fast Modular Subset Sum using Linear Sketching

Given n positive integers, the Modular Subset Sum problem asks if a subs...

0 Kyriakos Axiotis, et al. ∙

research

∙ 02/20/2018

Actively Avoiding Nonsense in Generative Models

A generative model may generate utter nonsense when it is fit to maximiz...

0 Steve Hanneke, et al. ∙

research

∙ 02/18/2018

Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

One of the most fundamental problems in Theoretical Computer Science is ...

0 Kyriakos Axiotis, et al. ∙

research

∙ 11/07/2017

Combinatorial Assortment Optimization

Assortment optimization refers to the problem of designing a slate of pr...

0 Nicole Immorlica, et al. ∙

research

∙ 09/12/2017

Certified Computation in Crowdsourcing

A wide range of learning tasks require human input in labeling massive d...

0 Themis Gouleakis, et al. ∙

research

∙ 02/23/2017

A Converse to Banach's Fixed Point Theorem and its CLS Completeness

Banach's fixed point theorem for contraction maps has been widely used t...

0 Constantinos Daskalakis, et al. ∙

research

∙ 01/02/2017

Truthful Facility Location with Additive Errors

We address the problem of locating facilities on the [0,1] interval base...

0 Iddan Golomb, et al. ∙

Christos Tzamos

Featured Co-authors