<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Yonatan Naamad will present his research seminar/general exam on Friday May 10 <br>at 1o:30 AM in room 302 (note time and room!). The members of his committee <br>are: Moses Charikar (advisor), Mark Braverman, and Zeev Dvir. Everyone is <br>invited to attend his talk and those faculty wishing to remain for the oral exam <br>following are welcome to do so. His abstract and reading list follow below.<br>-----------------------<br><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><p>
One measure of the complexity of a problem is its query
complexity, or the number of queries an algorithm must make to the
input in order to output a provably-correct solution. In this
talk, I'll discuss my work on establishing the query complexity of
the generalized sorting problem, where we wish to establish a
total order on a collection of n elements when the set of possible
pairwise comparisons is restricted to a certain subset of the
C(n,2) pairs of elements. If the subset is complete -- containing
all C(n,2) pairs -- then the query complexity of the problem is
well known to be Omega(n log n). In 2011, Huang, Kannan, and
Khanna gave the first nontrivial result in the more general
setting, establishing a (randomized) query complexity upper-bound
of O(n^(3/2) log n). We discuss recent improvements upon their
work.<br>
<br>
</p>
Based on joint work with Moses Charikar and Sampath Kannan.<br>
<br>
--<br>
<br>
and my reading list is<br>
<br>
<ol>
<li>(Book) Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein. Introduction to Algorithms, Third
Edition. The MIT Press, 2009.<br>
</li>
<li>Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor,
Rafail Ostrovsky: Matching Nuts and Bolts. SODA 1994: 690-696 </li>
<li> Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M.
Kleinberg, Prabhakar Raghavan, Amit Sahai: Query Strategies for
Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002)</li>
<li>Anupam Gupta, Amit Kumar: Sorting and Selection with
Structured Costs. FOCS 2001: 416-425<br>
</li>
<li>Zhiyi Huang, Sampath Kannan, Sanjeev Khanna: Algorithms for
the Generalized Sorting Problem. FOCS 2011: 738-747 </li>
<li>Jeff Kahn, Jeong Han Kim: Entropy and Sorting. J. Comput.
Syst. Sci. 51(3): 390-399 (1995)</li>
<li>Jeff Kahn, Nathan Linial: Balancing extensions via
Brunn-Minkowski. Combinatorica 11(4): 363-368 (1991)<br>
</li>
<li>Jeff Kahn, Michael E. Saks, Dean Sturtevant: A topological
approach to evasiveness. Combinatorica 4(4): 297-306 (1984)</li>
<li>Sampath Kannan, Sanjeev Khanna: Selection with monotone
comparison cost. SODA 2003: 10-17</li>
<li>Krzysztof Onak, Pawel Parys: Generalization of Binary Search:
Searching in Trees and Forest-Like Partial Orders. FOCS 2006:
379-388<br>
</li>
<li>Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are
Evasive. SIAM J. Comput. 17(3): 517-520 (1988)</li>
</ol><br></div><br></div></body></html>