[talks] Y Naamad general exam

[Melissa M. Lawson]

Yonatan Naamad will present his research seminar/general exam on Friday May 10 
at 1o:30 AM in room 302 (note time and room!). The members of his committee 
are: Moses Charikar (advisor), Mark Braverman, and Zeev Dvir. Everyone is 
invited to attend his talk and those faculty wishing to remain for the oral exam 
following are welcome to do so. His abstract and reading list follow below. 
----------------------- 


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. 

Based on joint work with Moses Charikar and Sampath Kannan. 

-- 

and my reading list is 



    1. (Book) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. 
    2. Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky: Matching Nuts and Bolts. SODA 1994: 690-696 
    3. 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) 
    4. Anupam Gupta, Amit Kumar: Sorting and Selection with Structured Costs. FOCS 2001: 416-425 
    5. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna: Algorithms for the Generalized Sorting Problem. FOCS 2011: 738-747 
    6. Jeff Kahn, Jeong Han Kim: Entropy and Sorting. J. Comput. Syst. Sci. 51(3): 390-399 (1995) 
    7. Jeff Kahn, Nathan Linial: Balancing extensions via Brunn-Minkowski. Combinatorica 11(4): 363-368 (1991) 
    8. Jeff Kahn, Michael E. Saks, Dean Sturtevant: A topological approach to evasiveness. Combinatorica 4(4): 297-306 (1984) 
    9. Sampath Kannan, Sanjeev Khanna: Selection with monotone comparison cost. SODA 2003: 10-17 
    10. Krzysztof Onak, Pawel Parys: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS 2006: 379-388 
    11. Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput. 17(3): 517-520 (1988) 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130506/2d3e5e4c/attachment.html>