Princeton Theory Group - Some Recent Publications
Under construction! last updated February 2006.
( * - student author)
2006
- Sanjeev Arora, Elad Hazan*, and Satyen Kale* "A Fast Random Sampling Algorithm for Sparsifying Matrices" RANDOM 2006
- Elad Hazan*, Adam Kalai, Satyen Kale* and Amit Agarwal* "Logarithmic Regret Algorithms for Online Convex Optimization" COLT 2006
- Amit Agarwal*, Elad Hazan*, Satyen Kale* and Robert E. Schapire "Algorithms for Portfolio Management based on the Newton Method" ICML 2006
- Abhiram Ranade, Srikanth S. M. and Satyen Kale* "A Variation on SVD Based Image Compression" WGVCIP 2006
- Nir Ailon*, Bernard Chazelle "Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform" to appear in STOC 2006
- Bernard Chazelle, Seshadhri Comandur* "Online Geometric Reconstruction" to appear in SOCG 2006
- Sanjeev Arora, Moses Charikar and Eden Chlamtac* "New Approximation Guarantees for Chromatic Number" to appear in STOC 2006
- Moses Charikar, MohammadTaghi Hajiaghayi, Howard Karloff and Satish Rao "l22 spreading metrics for vertex ordering problems" SODA 2006
- Nir Ailon*, Bernard Chazelle, Seshadhri Comandur*, and Ding Liu* "Self-Improving Algorithms" SODA 2006
- Moses Charikar and Samir Khuller "A Robust Maximum Completion Time Measure for Scheduling" SODA 2006
- Moses Charikar, Konstantin Makarychev* and Yury Makarychev* "Near-Optimal Algorithms for Unique Games" to appear in STOC 2006
- Moses Charikar, Konstantin Makarychev* and Yury Makarychev* "Directed Metrics and Directed Graph Partitioning Problems" SODA 2006
- Qin Lv*, William Josephson*, Zhe Wang*, Moses Charikar and Kai Li "Ferret: A Toolkit for Content-Based Similarity Search" to appear in EuroSys 2006
- Shengyu Zhang* " New upper and lower bounds for randomized and quantum Local Search", to appear in STOC 2006
- Wei Huang, Yaoyun Shi, Shengyu Zhang*, Yufan Zhu "The communication complexity of the Hamming Distance problem", IPL 2006.
- Robert Tarjan and Loukas Georgiadis* and Renato Werneck* "Design of Data Structures for Mergeable Trees" SODA 2006
- A. V. Goldberg and H. Kaplan and Renato Werneck* "Reach for A*: Efficient Point-to-Point Shortest Path Algorithms" ALENEX 2006
2005
- Sanjeev Arora, Elad Hazan*, and Satyen Kale* "Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method" FOCS 2005
- Satyen Kale*, Elad Hazan*, Fengyun Cao*, and J. P. Singh "Analysis and Algorithms for Content-based Event Matching" DEBS 2005
- Nir Ailon*, and Moses Charikar "Fitting tree metrics: Hierarchical Clustering and Phylogeny" FOCS 2005
- Moses Charikar, Chandra Chekuri and Martin Pal "Sampling Bounds for Stochastic Optimization" APPROX-RANDOM 2005
- Yael Kalai , Yehuda Lindell and Manoj Prabhakaran* "Concurrent General Composition of Secure Protocols in the Timing Model" STOC 2005
- Amit Agarwal*, Moses Charikar, Konstantin Makarychev*, Yury Makarychev* "O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems" STOC 2005
- Robert Tarjan and Renato Werneck* "Self-Adjusting Top Trees" SODA 2005
- A. V. Goldberg and Renato Werneck* "Computing Point-to-Point Shortest Paths from External Memory" ALENEX 2005
- Noga Alon, Konstantin Makarychev*, Yury Makarychev* and Assaf Naor "Quadratic forms on graphs" STOC 2005
- Amit Sahai and Manoj Prabhakaran* "Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation" TCC 2005
- Moses Charikar and Adriana Karagiozova* '"On Non-uniform Multicommodity Buy-at-Bulk Network Design"' STOC 2005
- Moses Charikar and Adriana Karagiozova* "A Tight Threshold for Metric Ramsey Phenomena" SODA 2005
- Eran Halperin and Elad Hazan* "HAPLOFREQ - Estimating Haplotype Frequencies Efficiently" RECOMB 2005
- Loukas Geordiadis* and Robert Tarjan "Dominator Tree Verification and Vertex-Disjoint Paths" SODA 2005
- Edith Elkind* "True Costs of Cheap Labor Are Hard To Measure: Edge Deletion and VCG Payments in Graphs" EC 2005
- Nir Ailon*, Moses Charikar and Alantha Newman "Aggregating Inconsistent Information: Ranking and Clustering" STOC 2005
- Sanjeev Arora, James Lee, and Assaf Naor "Euclidean distortion and the sparsest cut." STOC 2005
- Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala "Local versus global properties of metric spaces."
- Nir Ailon* and Bernard Chazelle '"Information Theory in Property Testing and Monotonicity Testing in Higher Dimension"' STACS 2005
- Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov and Avi Wigderson "Simulating Independence: New constructions ofCondensers, Dispersers, Ramsey Graphs, and Extractors" STOC 2005
- Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis* '"Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy"' STOC 2005
- Moses Charikar, Nikhil Bansal, Sanjeev Khanna and Seffi Naor 'Approximating the Average Response Time in Broadcast Scheduling' SODA 2005
- Shengyu Zhang* "Promised and distributed quantum search", COCOON 2005
- Shengyu Zhang* "On the power of Ambainis lower bounds", TCS 2005 (Prelim in ICALP 2004)
- Mung Chiang, Shengyu Zhang*, Prashanth Hande, "Distributed rate allocation for inelastic flows: optimization frameworks, optimality conditions and optimal algorithms", INFOCOM 2005
- Bernard Chazelle "Cuttings" Handbook of Data Structures and Applications, CRC Press 25 (2005), 25.1-25.10
- Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan "Approximating the Minimum Spanning Tree Weight in Sublinear Time" SIAM Journal on Computing, 34 (2005), 1370-1379
- E. Nabieva*, K. Jim*, A. Agarwal*, B. Chazelle, and M. Singh "Whole-Proteome Prediction of Protein Function via Graph-Theoretic Analysis of Interaction Maps" 13th ISMB (2005), 302-310.
2004
- Sanjeev Arora, Satish Rao, and Umesh Vazirani Expander Flows, Geometric Embeddings, and Graph Partitionings. STOC 2004 (Best paper award)
- Sanjeev Arora, Elad Hazan* and Satyen Kale* "O(sqrt(log n)) approximation to SPARSEST CUT can be found in Õ(n²) time" FOCS 2004
- Yevgenyi Dodis, Shein Jin Ong*, Amit Sahai and Manoj Prabhakaran* "On the (Im)possibility of Cryptography with Imperfect Randomness" FOCS 2004
- Sanjeev Arora and Bo Brinkman* "A Randomized Online Algorithm for Bandwidth Utilization" J. Scheduling 2004 Prelim version in SODA 2002
- M. G. C. Resende and Renato Werneck* "A hybrid heuristic for the p-median problem" J. of Heuristics, 2004
- L. Georgiadis*, R. E. Tarjan, S. Triantafyllis, Renato Werneck* and D. August Finding Dominators in Practice ESA 2004
- R. Fukasawa, J. Lysgaard, M. Poggi de Aragão, M. Reis, E. Uchoa and Renato Werneck* "Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem" IPCO 2004
- Ben Lynn, Amit Sahai and Manoj Prabhakaran* "Positive Results and Techniques for Obfuscation" EUROCRYPT 2004
- Nir Ailon, Bernard Chazelle, Seshadhri Comandur and Ding Liu* "Estimating the Distance to a Monotone Function" RANDOM 2004
- Ding Liu* "A Strong Lower Bound for Approximate Nearest Neighbor Searching in the Cell Probe Model" IPL 2004
- Ding Liu* "A Note on Point Location in Arrangements of Hyperplanes" IPL 2004
- Nir Ailon*, Bernard Chazelle, Seshadhri Comandur and Ding Liu* '"Property-Preserving Data Reconstruction"' ISAAC 2004
- Amit Sahai and Manoj Prabhakaran* New Notions of Security: Achieving Universal Composability without Trusted Setup" STOC 2004
- Loukas Geordiadis* and Robert Tarjan Finding Dominators Revisited SODA 2004
- Edith Elkind*, Amit Sahai and Ken Steiglitz Frugality in Path Auctions SODA 2004
- Nir Ailon* and Bernard Chazelle "Lower Bounds for Linear Degeneracy Testing" STOC 2004
- C.L. Kingsford, Bernard Chazelle and M. Singh "Solving and Analyzing Side-Chain Positioning Problems Using Linear and Integer Programming" Bioinformatics 2004
- Bernard Chazelle , J. Kilian, R. Rubinfeld, A. Tal "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables" SODA 2004
- Bernard Chazelle , Ding Liu*, A. Magen "Approximate Range Searching in Higher Dimension" CCCG 2004
- Bernard Chazelle "The Power of Nonmonotonicity in Geometric Searching" Disc. Comput. Geom. 2004
- Moses Charikar and Anthony Wirth* '"Maximizing quadratic programs: extending Grothendieck's inequality"' FOCS 2004
- Moses Charikar, Michel X. Goemans and Howard Karloff '"On the Integrality Ratio for Asymmetric TSP"' FOCS 2004 Qin Lv, [[ http://www.cs.princeton.edu/~moses |Moses Cha
|
|
|