5.2k citations
- Courant Institute of Mathematical SciencesUS5 papers
- University of Illinois Urbana-ChampaignUS4 papers
- University of WashingtonUS4 papers
- Columbia UniversityUS3 papers
- Cornell UniversityUS3 papers
- Massachusetts Institute of TechnologyUS3 papers
- Microsoft (United States)US3 papers
- New York UniversityUS3 papers
- Bharathidasan UniversityIN2 papers
- Laboratory for Atmospheric and Space PhysicsUS2 papers
- Microsoft Research (India)IN2 papers
- Rensselaer Polytechnic InstituteUS2 papers
15 papers · 1 filter
Optimal amortized regret in every interval
Rina Panigrahy, Preyas Popat
Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is {\em regret} (loss in payoff) with respect to a set of experts. F…
Fractal structures in Adversarial Prediction
Rina Panigrahy, Preyas Popat
Fractals are self-similar recursive structures that have been used in modeling several real world processes. In this work we study how "fractal-like" processes arise in a predictio…
Efficiency Guarantees in Auctions with Budgets
Shahar Dobzinski, Renato Paes Leme
In settings where players have a limited access to liquidity, represented in the form of budget constraints, efficiency maximization has proven to be a challenging goal. In particu…
Maximum degree in minor-closed classes of graphs
Omer Gimenez, Dieter Mitsche, Marc Noy
Given a class of graphs G closed under taking minors, we study the maximum degree Δ_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold wit…
Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu +7
We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…
Adversary Lower Bound for the Orthogonal Array Problem
Robert Spalek
We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array o…