# Seminars & Colloquia Calendar

## On the expressiveness of comparison queries

#### Shay Moran, IAS

Location: ** Hill 705**

Date & time: Monday, 23 April 2018 at 2:00PM - 3:00PM

Abstract: Comparisons are a classical and well studied algorithmic tool that is used in a variety of contexts and applications. We will discuss two manifestations of the expressiveness of these queries in machine learning and complexity theory (a more detailed overview is given below). Both manifestations are based on the notion of "inference dimension” that can be viewed as another instance of the fruitful link between machine learning and discrete mathematics - a link dating back to the discovery of the VC dimension.

Active classification with comparison queries [Kane, Lovett, Moran, Zhang ’17]

Active learning is a model for semi-supervised learning that captures situations in which unlabeled data is abundant and manually labelling it is expensive.

We consider an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We prove that the usage of comparison queries leads to an exponential improvement in the query complexity of some well studied problems. Specifically, for the class of half-spaces, we show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(logn) queries.

Nearly optimal linear decision trees for k-SUM and related problems [Kane, Lovett, Moran ’17]

We use the above framework to construct linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant k, we construct linear decision trees that solve the k-SUM problem on n elements using O(n log n) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two k-subsets; when viewed as linear queries, comparison queries are 2k-sparse and have only {-1,+1} coefficients.

We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms.

Charles Weibel Organizer's Page

Brooke Logan

Wujun Zhang Organizer's webpage

P. Gupta, X.Huang and J. Song Organizer's webpage

Swastik Kopparty, Sepehr Assadi Seminar webpage

Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage

Yonah Biers-Ariel, Mingjia Yang, and Doron Zeilberger --> homepage

Paul Feehan, Manousos Maridakis, Natasa Sesum Organizer's webpage

Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage

Jason Saied Seminar webpage

Brian Pinsky, Rashmika Goswami website

Corrine Yap Organizer's webpage

James Holland; Organizer website

Edna Jones Organizer's webpage

Brooke Ogrodnik website

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage

Simon Thomas website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Haim Brezis

Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Alex Walker seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Yael Davidov Seminar webpage

Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page

Ebru Toprak, Organizer

Fioralba Cakoni Seminar webpage

- Show events from all categories

## Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

*Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.*