13 citations · 16 across the 6 of their papers we have counts for
6 papers
The Sample Complexity of Multi-Distribution Learning for VC Classes
Pranjal Awasthi, Nika Haghtalab, Eric Zhao
Multi-distribution learning is a natural generalization of PAC learning to settings with multiple data distributions. There remains a significant gap between the known upper and lo…
Smoothed Analysis of Sequential Probability Assignment
Alankrita Bhatt, Nika Haghtalab, Abhishek Shetty
We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a fra…
Stochastic Minimum Vertex Cover in General Graphs: a -Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
Our main result is designing an algorithm that returns a vertex cover of with size at most times the expected size of the minimum vertex cover, using…
Generalized Topic Modeling
Avrim Blum, Nika Haghtalab
Recently there has been significant activity in developing algorithms with provable guarantees for topic modeling. In standard topic models, a topic (such as sports, business, or p…
Opting Into Optimal Matchings
Avrim Blum, Ioannis Caragiannis, Nika Haghtalab +3
We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player --- who is as…
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Avrim Blum, John P. Dickerson, Nika Haghtalab +3
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic -s…