88 citations · 311 across the 59 of their papers we have counts for
7 papers · 1 filter
Pandora's Box with Correlations: Learning and Approximation
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng +2
The Pandora's Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cos…
Efficient Truncated Statistics with Unknown Truncation
Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis
We study the problem of estimating the parameters of a Gaussian distribution when samples are only shown if they fall in some (unknown) subset . This core problem…
The Complexity of Black-Box Mechanism Design with Priors
Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an u…
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…
Diversity and Exploration in Social Learning
Nicole Immorlica, Jieming Mao, Christos Tzamos
In consumer search, there is a set of items. An agent has a prior over her value for each item and can pay a cost to learn the instantiation of her value. After exploring a subset…
Learning to Prune: Speeding up Repeated Computations
Daniel Alabi, Adam Tauman Kalai, Katrina Ligett +3
It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each inst…
Buy-many mechanisms are not much better than item pricing
Shuchi Chawla, Yifeng Teng, Christos Tzamos
Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps…