Timezone: »

 
Poster
Maxing and Ranking with Few Assumptions
Moein Falahatgar · Yi Hao · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #40
in Posters Mon »
PAC maximum selection (maxing) and ranking of $n$ elements via random pairwise comparisons have diverse applications and have been studied under many models and assumptions. With just one simple natural assumption: strong stochastic transitivity, we show that maxing can be performed with linearly many comparisons yet ranking requires quadratically many. With no assumptions at all, we show that for the Borda-score metric, maximum selection can be performed with linearly many comparisons and ranking can be performed with $\mathcal{O}(n\log n)$ comparisons.
Keywords: Online Learning · Ranking and Preference Learning
[ Paper] 

Author Information

Moein Falahatgar (UCSD)
Yi Hao (UCSD)
Alon Orlitsky (University of California, San Diego)
Venkatadheeraj Pichapati (UC San Diego)
Vaishakh Ravindrakumar (UC San Diego)

More from the Same Authors