|
[1]
|
Benny Applebaum, Boaz Barak, and David Xiao.
On basing lower-bounds for learning on worst-case assumptions.
In FOCS, pages 211-220, 2008.
[ doi ]
|
|
[2]
|
Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani,
and Nisheeth K. Vishnoi.
Unique games on expanding constraint graphs are easy: extended
abstract.
In STOC, pages 21-28, 2008.
[ doi ]
|
|
[3]
|
Boaz Barak, Sharon Goldberg, and David Xiao.
Protocols and lower bounds for failure localization in the internet.
In EUROCRYPT, pages 341-360, 2008.
[ doi ]
|
|
[4]
|
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer.
Rounding parallel repetitions of unique games.
In FOCS, pages 374-383, 2008.
[ doi ]
|
|
[5]
|
Markus Bläser, Moritz Hardt, and David Steurer.
Asymptotically optimal hitting sets against polynomials.
In ICALP (1), pages 345-356, 2008.
[ doi ]
|
|
[6]
|
Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, and Michael E.
Saks.
Online multicast with egalitarian cost sharing.
In SPAA, pages 70-76, 2008.
[ doi ]
|
|
[7]
|
Bernard Chazelle and Wolfgang Johann Heinrich Mulzer.
Markov incremental constructions.
In Symposium on Computational Geometry, pages 156-163, 2008.
[ doi ]
|
|
[8]
|
Eden Chlamtac and Gyanit Singh.
Improved approximation guarantees through higher levels of sdp
hierarchies.
In APPROX-RANDOM, pages 49-62, 2008.
[ doi ]
|
|
[9]
|
Kenneth L. Clarkson and C. Seshadhri.
Self-improving algorithms for delaunay triangulations.
In Symposium on Computational Geometry, pages 148-155, 2008.
[ doi ]
|
|
[10]
|
Wei Dong, Moses Charikar, and Kai Li.
Asymmetric distance estimation with sketches for similarity search in
high-dimensional spaces.
In SIGIR, pages 123-130, 2008.
[ doi ]
|
|
[11]
|
Wei Dong, Zhe Wang, Moses Charikar, and Kai Li.
Efficiently matching sets of features with random histograms.
In ACM Multimedia, pages 179-188, 2008.
[ doi ]
|
|
[12]
|
Wei Dong, Zhe Wang, William Josephson, Moses Charikar, and Kai Li.
Modeling lsh for performance tuning.
In CIKM, pages 669-678, 2008.
[ doi ]
|
|
[13]
|
Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber,
and Robert Endre Tarjan.
Fast exact and heuristic methods for role minimization problems.
In SACMAT, pages 1-10, 2008.
[ doi ]
|
|
[14]
|
Sharon Goldberg, Shai Halevi, Aaron D. Jaggard, Vijay Ramachandran, and
Rebecca N. Wright.
Rationality and traffic attraction: incentives for honest path
announcements in bgp.
In SIGCOMM, pages 267-278, 2008.
[ doi ]
|
|
[15]
|
Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford.
Path-quality monitoring in the presence of adversaries.
In SIGMETRICS, pages 193-204, 2008.
[ doi ]
|
|
[16]
|
Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra.
Beating the random ordering is hard: Inapproximability of maximum
acyclic subgraph.
In FOCS, pages 573-582, 2008.
[ doi ]
|
|
[17]
|
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and
Robert Endre Tarjan.
Faster algorithms for incremental topological ordering.
In ICALP (1), pages 421-433, 2008.
[ doi ]
|
|
[18]
|
J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William
Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W.
Felten.
Lest we remember: Cold boot attacks on encryption keys.
In USENIX Security Symposium, pages 45-60, 2008.
[ doi ]
|
|
[19]
|
Elad Hazan and Satyen Kale.
Computational equivalence of fixed points and no regret algorithms,
and convergence to equilibria.
In NIPS, 2007.
[ doi ]
|
|
[20]
|
Satyen Kale, Yuval Peres, and C. Seshadhri.
Noise tolerance of expanders and sublinear expander reconstruction.
In FOCS, pages 719-728, 2008.
[ doi ]
|
|
[21]
|
Satyen Kale and C. Seshadhri.
An expansion tester for bounded degree graphs.
In ICALP (1), pages 527-538, 2008.
[ doi ]
|
|
[22]
|
Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, and Roy Schwartz.
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric
labeling.
In STOC, pages 11-20, 2008.
[ doi ]
|
|
[23]
|
Dana Moshkovitz and Ran Raz.
Two query pcp with sub-constant error.
In FOCS, pages 314-323, 2008.
[ doi ]
|
|
[24]
|
Michael E. Saks and C. Seshadhri.
Parallel monotonicity reconstruction.
In SODA, pages 962-971, 2008.
[ doi ]
|
|
[25]
|
Robert Endre Tarjan.
Reachability problems on directed graphs.
In ISAAC, page 3, 2008.
[ doi ]
|
|
[26]
|
Greg Wilson, Christine Alvarado, Jennifer Campbell, Rubin H. Landau, and Robert
Sedgewick.
Cs-1 for scientists.
In SIGCSE, pages 36-37, 2008.
[ doi ]
|
|
[1]
|
Amit Agarwal, Noga Alon, and Moses Charikar.
Improved approximation for directed cut problems.
In STOC, pages 671-680, 2007.
[ doi ]
|
|
[2]
|
Elliot Anshelevich and Adriana Karagiozova.
Terminal backup, 3d matching, and covering cubic graphs.
In STOC, pages 391-400, 2007.
[ doi ]
|
|
[3]
|
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz.
Cryptography with constant input locality.
In CRYPTO, pages 92-110, 2007.
[ doi ]
|
|
[4]
|
Sanjeev Arora and Satyen Kale.
A combinatorial, primal-dual approach to semidefinite programs.
In STOC, pages 227-236, 2007.
[ doi ]
|
|
[5]
|
Maxim A. Babenko, Jonathan Derryberry, Andrew V. Goldberg, Robert Endre Tarjan,
and Yunhong Zhou.
Experimental evaluation of parametric max-flow algorithms.
In WEA, pages 256-269, 2007.
[ doi ]
|
|
[6]
|
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and
Kunal Talwar.
Privacy, accuracy, and consistency too: a holistic solution to
contingency table release.
In PODS, pages 273-282, 2007.
[ doi ]
|
|
[7]
|
Boaz Barak and Mohammad Mahmoody-Ghidary.
Lower bounds on signatures from symmetric primitives.
In FOCS, pages 680-688, 2007.
[ doi ]
|
|
[8]
|
Bo Brinkman, Adriana Karagiozova, and James R. Lee.
Vertex cuts, random walks, and dimension reduction in series-parallel
graphs.
In STOC, pages 621-630, 2007.
[ doi ]
|
|
[9]
|
Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
On the advantage over random for maximum acyclic subgraph.
In FOCS, pages 625-633, 2007.
[ doi ]
|
|
[10]
|
Bernard Chazelle.
Ushering in a new era of algorithm design.
In ICALP, page 1, 2007.
[ doi ]
|
|
[11]
|
Eden Chlamtac.
Approximation algorithms using hierarchies of semidefinite
programming relaxations.
In FOCS, pages 691-701, 2007.
[ doi ]
|
|
[12]
|
Elad Hazan and Satyen Kale.
Computational equivalence of fixed points and no regret algorithms,
and convergence to equilibria.
In NIPS, 2007.
[ doi ]
|
|
[13]
|
T. S. Jayram, Satyen Kale, and Erik Vee.
Efficient aggregation algorithms for probabilistic data.
In SODA, pages 346-355, 2007.
[ doi ]
|
|
[14]
|
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li.
Multi-probe lsh: Efficient indexing for high-dimensional similarity
search.
In VLDB, pages 950-961, 2007.
[ doi ]
|
|
[15]
|
Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert Endre Tarjan.
Clustering social networks.
In WAW, pages 56-67, 2007.
[ doi ]
|
|
[16]
|
Robert Endre Tarjan and Renato Fonseca F. Werneck.
Dynamic trees in practice.
In WEA, pages 80-93, 2007.
[ doi ]
|
|
[17]
|
Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, and Kai Li.
Sizing sketches: a rank-based analysis for similarity search.
In SIGMETRICS, pages 157-168, 2007.
[ doi ]
|
|
[1]
|
Amit Agarwal, Elad Hazan, Satyen Kale, and Robert E. Schapire.
Algorithms for portfolio management based on the newton method.
In ICML, pages 9-16, 2006.
[ doi ]
|
|
[2]
|
Nir Ailon and Bernard Chazelle.
Approximate nearest neighbors and the fast johnson-lindenstrauss
transform.
In STOC, pages 557-563, 2006.
[ doi ]
|
|
[3]
|
Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu.
Self-improving algorithms.
In SODA, pages 261-270, 2006.
[ doi ]
|
|
[4]
|
Nir Ailon, Steve Chien, and Cynthia Dwork.
On clusters in markov chains.
In LATIN, pages 43-55, 2006.
[ doi ]
|
|
[5]
|
Lars Arge, Robert Sedgewick, and Dorothea Wagner.
06091 executive summary - data structures.
In Data Structures, 2006.
[ doi ]
|
|
[6]
|
Sanjeev Arora and Eden Chlamtac.
New approximation guarantee for chromatic number.
In STOC, pages 215-224, 2006.
[ doi ]
|
|
[7]
|
Sanjeev Arora, Elad Hazan, and Satyen Kale.
A fast random sampling algorithm for sparsifying matrices.
In APPROX-RANDOM, pages 272-279, 2006.
[ doi ]
|
|
[8]
|
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri
Rabinovich, and Santosh Vempala.
Local versus global properties of metric spaces.
In SODA, pages 41-50, 2006.
[ doi ]
|
|
[9]
|
Boaz Barak.
Non-black-box techniques in cryptography.
In CSR, page 1, 2006.
[ doi ]
|
|
[10]
|
Boaz Barak, Manoj Prabhakaran, and Amit Sahai.
Concurrent non-malleable zero knowledge.
In FOCS, pages 345-354, 2006.
[ doi ]
|
|
[11]
|
Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson.
2-source dispersers for sub-polynomial entropy and ramsey graphs
beating the frankl-wilson construction.
In STOC, pages 671-680, 2006.
[ doi ]
|
|
[12]
|
MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Erik D. Demaine, and
Mohammad Moharrami.
Plane embeddings of planar graph metrics.
In Symposium on Computational Geometry, pages 197-206, 2006.
[ doi ]
|
|
[13]
|
Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, and Satish Rao.
22 spreading metrics for vertex
ordering problems.
In SODA, pages 1018-1027, 2006.
[ doi ]
|
|
[14]
|
Moses Charikar and Samir Khuller.
A robust maximum completion time measure for scheduling.
In SODA, pages 324-333, 2006.
[ doi ]
|
|
[15]
|
Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
Directed metrics and directed graph partitioning problems.
In SODA, pages 51-60, 2006.
[ doi ]
|
|
[16]
|
Bernard Chazelle, Ding Liu, and Avner Magen.
Sublinear geometric algorithms.
In Sublinear Algorithms, 2005.
[ doi ]
|
|
[17]
|
Bernard Chazelle and C. Seshadhri.
Online geometric reconstruction.
In Symposium on Computational Geometry, pages 386-394, 2006.
[ doi ]
|
|
[18]
|
Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev.
How to play unique games using embeddings.
In FOCS, pages 687-696, 2006.
[ doi ]
|
|
[19]
|
Benjamin Doerr, Johannes Lengler, and David Steurer.
The interval liar game.
In ISAAC, pages 318-327, 2006.
[ doi ]
|
|
[20]
|
Loukas Georgiadis, Robert Endre Tarjan, and Renato Fonseca F. Werneck.
Design of data structures for mergeable trees.
In SODA, pages 394-403, 2006.
[ doi ]
|
|
[21]
|
Elad Hazan, Adam Kalai, Satyen Kale, and Amit Agarwal.
Logarithmic regret algorithms for online convex optimization.
In COLT, pages 499-513, 2006.
[ doi ]
|
|
[22]
|
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li.
Ferret: a toolkit for content-based similarity search of feature-rich
data.
In EuroSys, pages 317-330, 2006.
[ doi ]
|
|
[23]
|
Wolfgang Mulzer and Günter Rote.
Minimum weight triangulation is np-hard.
In Symposium on Computational Geometry, pages 1-10, 2006.
[ doi ]
|
|
[24]
|
Nan Song, Robert Sedgewick, and Dannie Durand.
Domain architecture in homolog identification.
In Comparative Genomics, pages 11-23, 2006.
[ doi ]
|
|
[25]
|
David Steurer.
Tight bounds for the min-max boundary decomposition cost of weighted
graphs.
In SPAA, pages 197-206, 2006.
[ doi ]
|
|
[26]
|
Robert Endre Tarjan.
Results and problems on self-adjusting search trees and related data
structures.
In SWAT, page 2, 2006.
[ doi ]
|
|
[27]
|
Robert Endre Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, and Jia Mao.
Balancing applied to maximum network flow problems.
In ESA, pages 612-623, 2006.
[ doi ]
|
|
[28]
|
Iannis Tourlakis.
New lower bounds for vertex cover in the lovasz-schrijver hierarchy.
In IEEE Conference on Computational Complexity, pages 170-182,
2006.
[ doi ]
|
|
[1]
|
Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
O(sqrt(log n)) approximation algorithms for min uncut, min 2cnf
deletion, and directed cut problems.
In STOC, pages 573-581, 2005.
[ doi ]
|
|
[2]
|
Nir Ailon and Moses Charikar.
Fitting tree metrics: Hierarchical clustering and phylogeny.
In FOCS, pages 73-82, 2005.
[ doi ]
|
|
[3]
|
Nir Ailon, Moses Charikar, and Alantha Newman.
Aggregating inconsistent information: ranking and clustering.
In STOC, pages 684-693, 2005.
[ doi ]
|
|
[4]
|
Susanne Albers, Robert Sedgewick, and Dorothea Wagner.
04091 abstracts collection - data structures.
In Data Structures, 2004.
[ doi ]
|
|
[5]
|
Michael Alekhnovich, Sanjeev Arora, and Iannis Tourlakis.
Towards strong nonapproximability results in the lovasz-schrijver
hierarchy.
In STOC, pages 294-303, 2005.
[ doi ]
|
|
[6]
|
Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor.
Quadratic forms on graphs.
In STOC, pages 486-493, 2005.
[ doi ]
|
|
[7]
|
Eric Anderson, Dirk Beyer 0002, Kamalika Chaudhuri, Terence Kelly, Norman
Salazar, Cipriano A. Santos, Ram Swaminathan, Robert Endre Tarjan, Janet L.
Wiener, and Yunhong Zhou.
Deadline scheduling for animation rendering.
In SIGMETRICS, pages 384-385, 2005.
[ doi ]
|
|
[8]
|
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra.
On non-approximability for quadratic programs.
In FOCS, pages 206-215, 2005.
[ doi ]
|
|
[9]
|
Sanjeev Arora, Elad Hazan, and Satyen Kale.
Fast algorithms for approximate semide.nite programming using the
multiplicative weights update method.
In FOCS, pages 339-348, 2005.
[ doi ]
|
|
[10]
|
Sanjeev Arora, James R. Lee, and Assaf Naor.
Euclidean distortion and the sparsest cut.
In STOC, pages 553-562, 2005.
[ doi ]
|
|
[11]
|
Nikhil Bansal, Moses Charikar, Sanjeev Khanna, and Joseph Naor.
Approximating the average response time in broadcast scheduling.
In SODA, pages 215-221, 2005.
[ doi ]
|
|
[12]
|
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin.
Secure computation without authentication.
In CRYPTO, pages 361-377, 2005.
[ doi ]
|
|
[13]
|
Boaz Barak and Shai Halevi.
A model and architecture for pseudo-random generation with
applications to /dev/random.
In ACM Conference on Computer and Communications Security,
pages 203-212, 2005.
[ doi ]
|
|
[14]
|
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson.
Simulating independence: new constructions of condensers, ramsey
graphs, dispersers, and extractors.
In STOC, pages 1-10, 2005.
[ doi ]
|
|
[15]
|
Boaz Barak and Amit Sahai.
How to play almost any mental game over the net - concurrent
composition via super-polynomial simulation.
In FOCS, pages 543-552, 2005.
[ doi ]
|
|
[16]
|
Moses Charikar, Chandra Chekuri, and Martin Pál.
Sampling bounds for stochastic optimization.
In APPROX-RANDOM, pages 257-269, 2005.
[ doi ]
|
|
[17]
|
Moses Charikar and Adriana Karagiozova.
A tight threshold for metric ramsey phenomena.
In SODA, pages 129-136, 2005.
[ doi ]
|
|
[18]
|
Kamalika Chaudhuri, Anshul Kothari, Rudi Pendavingh, Ram Swaminathan,
Robert Endre Tarjan, and Yunhong Zhou.
Server allocation algorithms for tiered systems.
In COCOON, pages 632-643, 2005.
[ doi ]
|
|
[19]
|
Bernard Chazelle.
Algorithmic techniques and tools from computational geometry.
In FOCS, page 7, 2005.
[ doi ]
|
|
[20]
|
Bernard Chazelle, Ding Liu, and Avner Magen.
Sublinear geometric algorithms.
In Sublinear Algorithms, 2005.
[ doi ]
|
|
[21]
|
Seshadhri Comandur, Anil Seth, and Somenath Biswas.
Ram simulation of bgs model of abstract state machines.
In Abstract State Machines, pages 377-386, 2005.
[ doi ]
|
|
[22]
|
Edith Elkind.
True costs of cheap labor are hard to measure: edge deletion and vcg
payments in graphs.
In ACM Conference on Electronic Commerce, pages 108-116, 2005.
[ doi ]
|
|
[23]
|
Edith Elkind and Helger Lipmaa.
Small coalitions cannot manipulate voting.
In Financial Cryptography, pages 285-297, 2005.
[ doi ]
|
|
[24]
|
Loukas Georgiadis and Robert Endre Tarjan.
Dominator tree verification and vertex-disjoint paths.
In SODA, pages 433-442, 2005.
[ doi ]
|
|
[25]
|
Eran Halperin and Elad Hazan.
Haplofreq - estimating haplotype frequencies e.ciently.
In RECOMB, pages 553-568, 2005.
[ doi ]
|
|
[26]
|
Yael Tauman Kalai, Yehuda Lindell, and Manoj Prabhakaran.
Concurrent general composition of secure protocols in the timing
model.
In STOC, pages 644-653, 2005.
[ doi ]
|
|
[27]
|
Satyen Kale, Elad Hazan, Fengyun Cao, and Jaswinder Pal Singh.
Analysis and algorithms for content-based event matching.
In ICDCS Workshops, pages 363-369, 2005.
[ doi ]
|
|
[28]
|
Elena Nabieva, Kam Jim, Amit Agarwal, Bernard Chazelle, and Mona Singh.
Whole-proteome prediction of protein function via graph-theoretic
analysis of interaction maps.
In ISMB (Supplement of Bioinformatics), pages 302-310, 2005.
[ doi ]
|
|
[29]
|
Manoj Prabhakaran and Amit Sahai.
Relaxing environmental security: Monitored functionalities and
client-server computation.
In TCC, pages 104-127, 2005.
[ doi ]
|
|
[30]
|
Robert Endre Tarjan and Renato Fonseca F. Werneck.
Self-adjusting top trees.
In SODA, pages 813-822, 2005.
[ doi ]
|
|
[31]
|
Iannis Tourlakis.
Towards optimal integrality gaps for hypergraph vertex cover in the
lovász-schrijver hierarchy.
In APPROX-RANDOM, pages 233-244, 2005.
[ doi ]
|
|
[32]
|
Avi Wigderson and David Xiao.
A randomness-efficient sampler for matrix-valued functions and
applications.
In FOCS, pages 397-406, 2005.
[ doi ]
|
|
[1]
|
Nir Ailon and Bernard Chazelle.
Lower bounds for linear degeneracy testing.
In STOC, pages 554-560, 2004.
[ doi ]
|
|
[2]
|
Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu.
Estimating the distance to a monotone function.
In APPROX-RANDOM, pages 229-236, 2004.
[ doi ]
|
|
[3]
|
Susanne Albers, Robert Sedgewick, and Dorothea Wagner.
04091 abstracts collection - data structures.
In Data Structures, 2004.
[ doi ]
|
|
[4]
|
Sanjeev Arora, Elad Hazan, and Satyen Kale.
0(sqrt (log n)) approximation to sparsest cut in
õ(n2) time.
In FOCS, pages 238-247, 2004.
[ doi ]
|
|
[5]
|
Sanjeev Arora, Satish Rao, and Umesh V. Vazirani.
Expander flows, geometric embeddings and graph partitioning.
In STOC, pages 222-231, 2004.
[ doi ]
|
|
[6]
|
Moses Charikar, Michel X. Goemans, and Howard J. Karloff.
On the integrality ratio for asymmetric tsp.
In FOCS, pages 101-107, 2004.
[ doi ]
|
|
[7]
|
Moses Charikar and Anthony Wirth.
Maximizing quadratic programs: Extending grothendieck's inequality.
In FOCS, pages 54-60, 2004.
[ doi ]
|
|
[8]
|
Bernard Chazelle.
Who says you have to look at the input? the brave new world of
sublinear computing.
In SODA, page 141, 2004.
[ doi ]
|
|
[9]
|
Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal.
The bloomier filter: an efficient data structure for static support
lookup tables.
In SODA, pages 30-39, 2004.
[ doi ]
|
|
[10]
|
Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao.
Fisher equilibrium price with a class of concave utility functions.
In ESA, pages 169-179, 2004.
[ doi ]
|
|
[11]
|
Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, and Amit Sahai.
On the (im)possibility of cryptography with imperfect randomness.
In FOCS, pages 196-205, 2004.
[ doi ]
|
|
[12]
|
Edith Elkind and Helger Lipmaa.
Interleaving cryptography and mechanism design: The case of online
auctions.
In Financial Cryptography, pages 117-131, 2004.
[ doi ]
|
|
[13]
|
Edith Elkind, Amit Sahai, and Kenneth Steiglitz.
Frugality in path auctions.
In SODA, pages 701-709, 2004.
[ doi ]
|
|
[14]
|
Loukas Georgiadis and Robert Endre Tarjan.
Finding dominators revisited: extended abstract.
In SODA, pages 869-878, 2004.
[ doi ]
|
|
[15]
|
Loukas Georgiadis, Renato Fonseca F. Werneck, Robert Endre Tarjan, Spyridon
Triantafyllis, and David I. August.
Finding dominators in practice.
In ESA, pages 677-688, 2004.
[ doi ]
|
|
[16]
|
Sharon Goldberg, Stephen Liu, Sean Nicolson, and Khoman Phang.
Cmos limiting optical preamplifiers using dynamic biasing for wide
dynamic range.
In ISCAS (4), pages 217-220, 2004.
|
|
[17]
|
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai.
Batch codes and their applications.
In STOC, pages 262-271, 2004.
[ doi ]
|
|
[18]
|
Ding Liu, Bernard Chazelle, and Avner Magen.
Approximate range searching in higher dimension.
In CCCG, pages 154-157, 2004.
[ doi ]
|
|
[19]
|
Qin Lv, Moses Charikar, and Kai Li.
Image similarity search with compact data structures.
In CIKM, pages 208-217, 2004.
[ doi ]
|
|
[20]
|
Ben Lynn, Manoj Prabhakaran, and Amit Sahai.
Positive results and techniques for obfuscation.
In EUROCRYPT, pages 20-39, 2004.
[ doi ]
|
|
[21]
|
Ran Mendelson, Robert Endre Tarjan, Mikkel Thorup, and Uri Zwick.
Melding priority queues.
In SWAT, pages 223-235, 2004.
[ doi ]
|
|
[22]
|
Manoj Prabhakaran and Amit Sahai.
New notions of security: achieving universal composability without
trusted setup.
In STOC, pages 242-251, 2004.
[ doi ]
|
|
[23]
|
Amit Sahai.
Secure protocols for complex tasks in complex environments.
In INDOCRYPT, pages 14-16, 2004.
[ doi ]
|
|
[24]
|
Xiaoming Sun, Andrew Chi-Chih Yao, and Shengyu Zhang.
Graph properties and circular functions: How low can quantum query
complexity go?
In IEEE Conference on Computational Complexity, pages 286-293,
2004.
[ doi ]
|
|
[25]
|
Andrew Chi-Chih Yao.
Graph entropy and quantum sorting problems.
In STOC, pages 112-117, 2004.
[ doi ]
|
|
[1]
|
Eric Allender, Sanjeev Arora, Michael S. Kearns, Cristopher Moore, and
Alexander Russell.
A note on the representational incompatibility of function
approximation and factored dynamics.
In NIPS, pages 431-437, 2002.
[ doi ]
|
|
[2]
|
Sanjeev Arora.
Proving integrality gaps without knowing the linear program.
In FCT, page 1, 2003.
[ doi ]
|
|
[3]
|
Sanjeev Arora and Kevin L. Chang.
Approximation schemes for degree-restricted mst and red-blue
separation problem.
In ICALP, pages 176-188, 2003.
[ doi ]
|
|
[4]
|
Bo Brinkman and Moses Charikar.
On the impossibility of dimension reduction in l1.
In FOCS, pages 514-523, 2003.
[ doi ]
|
|
[5]
|
Amit Chakrabarti, Subhash Khot, and Xiaodong Sun.
Near-optimal lower bounds on the multi-party communication complexity
of set disjointness.
In IEEE Conference on Computational Complexity, pages 107-117,
2003.
[ doi ]
|
|
[6]
|
Moses Charikar, Venkatesan Guruswami, and Anthony Wirth.
Clustering with qualitative information.
In FOCS, pages 524-533, 2003.
[ doi ]
|
|
[7]
|
Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy.
Better streaming algorithms for clustering problems.
In STOC, pages 30-39, 2003.
[ doi ]
|
|
[8]
|
Bernard Chazelle.
Sublinear computing.
In ESA, page 1, 2003.
[ doi ]
|
|
[9]
|
Bernard Chazelle, Carl Kingsford, and Mona Singh.
The side-chain positioning problem: A semidefinite programming
formulation with new rounding schemes.
In PCK50, pages 86-94, 2003.
|
|
[10]
|
Bernard Chazelle, Ding Liu, and Avner Magen.
Sublinear geometric algorithms.
In STOC, pages 531-540, 2003.
[ doi ]
|
|
[11]
|
Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev.
A new multilayered pcp and the hardness of hypergraph vertex cover.
In STOC, pages 595-601, 2003.
[ doi ]
|
|
[12]
|
Inge Li Gørtz and Anthony Wirth.
Asymmetry in k-center variants.
In RANDOM-APPROX, pages 59-70, 2003.
[ doi ]
|
|
[13]
|
Stuart Haber, Bill G. Horne, Joe Pato, Tomas Sander, and Robert Endre Tarjan.
If piracy is the problem, is drm the answer?
In Digital Rights Management, pages 224-233, 2003.
[ doi ]
|
|
[14]
|
Elad Hazan, Shmuel Safra, and Oded Schwartz.
On the complexity of approximating k-dimensional matching.
In RANDOM-APPROX, pages 83-97, 2003.
[ doi ]
|
|
[15]
|
Jonas Holmerin and Subhash Khot.
A strong inapproximability gap for a generalization of minimum
bisection.
In IEEE Conference on Computational Complexity, pages 371-378,
2003.
[ doi ]
|
|
[16]
|
Yuval Ishai, Amit Sahai, and David Wagner.
Private circuits: Securing hardware against probing attacks.
In CRYPTO, pages 463-481, 2003.
[ doi ]
|
|
[17]
|
T. S. Jayram, Subhash Khot, Ravi Kumar, and Yuval Rabani.
Cell-probe lower bounds for the partial match problem.
In STOC, pages 667-672, 2003.
[ doi ]
|
|
[18]
|
Haim Kaplan, Eyal Molad, and Robert Endre Tarjan.
Dynamic rectangular intersection with priorities.
In STOC, pages 639-648, 2003.
[ doi ]
|
|
[19]
|
Subhash Khot.
Hardness of approximating the shortest vector problem in high lp
norms.
In FOCS, pages 290-297, 2003.
[ doi ]
|
|
[20]
|
Subhash Khot and Oded Regev.
Vertex cover might be hard to approximate to within 2-ε.
In IEEE Conference on Computational Complexity, pages 379-,
2003.
[ doi ]
|
|
[21]
|
Brent R. Waters, Edward W. Felten, and Amit Sahai.
Receiver anonymity via incomparable public keys.
In ACM Conference on Computer and Communications Security,
pages 112-121, 2003.
[ doi ]
|
|
[22]
|
Andrew Chi-Chih Yao.
Interactive proofs for quantum computation.
In ISAAC, page 1, 2003.
[ doi ]
|
|
[1]
|
Eric Allender, Sanjeev Arora, Michael S. Kearns, Cristopher Moore, and
Alexander Russell.
A note on the representational incompatibility of function
approximation and factored dynamics.
In NIPS, pages 431-437, 2002.
[ doi ]
|
|
[2]
|
Sanjeev Arora, Béla Bollobás, and László Lovász.
Proving integrality gaps without knowing the linear program.
In FOCS, pages 313-322, 2002.
[ doi ]
|
|
[3]
|
Sanjeev Arora and Bo Brinkman.
A randomized online algorithm for bandwidth utilization.
In SODA, pages 535-539, 2002.
[ doi ]
|
|
[4]
|
Sanjeev Arora and Subhash Khot.
Fitting algebraic curves to noisy data.
In STOC, pages 162-169, 2002.
[ doi ]
|
|
[5]
|
Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani.
Improved approximation algorithms for resource allocation.
In IPCO, pages 401-414, 2002.
[ doi ]
|
|
[6]
|
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai.
Universally composable two-party and multi-party secure computation.
In STOC, pages 494-503, 2002.
[ doi ]
|
|
[7]
|
Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar.
Approximation algorithms for the unsplittable flow problem.
In APPROX, pages 51-66, 2002.
[ doi ]
|
|
[8]
|
Moses Charikar.
On semidefinite programming relaxations for graph coloring and vertex
cover.
In SODA, pages 616-620, 2002.
[ doi ]
|
|
[9]
|
Moses Charikar, Kevin Chen, and Martin Farach-Colton.
Finding frequent items in data streams.
In ICALP, pages 693-703, 2002.
[ doi ]
|
|
[10]
|
Moses Charikar, Piotr Indyk, and Rina Panigrahy.
New algorithms for subset query, partial match, orthogonal range
searching, and related problems.
In ICALP, pages 451-462, 2002.
[ doi ]
|
|
[11]
|
Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April
Rasala, Amit Sahai, and Abhi Shelat.
Approximating the smallest grammar: Kolmogorov complexity in natural
models.
In STOC, pages 792-801, 2002.
[ doi ]
|
|
[12]
|
Moses Charikar and Amit Sahai.
Dimension reduction in the _1 norm.
In FOCS, pages 551-560, 2002.
[ doi ]
|
|
[13]
|
Bernard Chazelle.
The power of nonmonotonicity in geometric searching.
In Symposium on Computational Geometry, pages 88-93, 2002.
[ doi ]
|
|
[14]
|
Bill G. Horne, Lesley R. Matheson, Casey Sheehan, and Robert Endre Tarjan.
Dynamic self-checking techniques for improved tamper resistance.
In Digital Rights Management Workshop, pages 141-159, 2001.
[ doi ]
|
|
[15]
|
Haim Kaplan, Nira Shafrir, and Robert Endre Tarjan.
Union-find with deletions.
In SODA, pages 19-28, 2002.
[ doi ]
|
|
[16]
|
Michael M. Kazhdan, Bernard Chazelle, David P. Dobkin, Adam Finkelstein, and
Thomas A. Funkhouser.
A reflective symmetry descriptor.
In ECCV (2), pages 642-656, 2002.
[ doi ]
|
|
[17]
|
Subhash Khot.
On the power of unique 2-prover 1-round games.
In IEEE Conference on Computational Complexity, page 25, 2002.
[ doi ]
|
|
[18]
|
Ding Liu and Manoj Prabhakaran.
On randomized broadcasting and gossiping in radio networks.
In COCOON, pages 340-349, 2002.
[ doi ]
|
|
[19]
|
Manoj Prabhakaran, Alon Rosen, and Amit Sahai.
Concurrent zero knowledge with logarithmic round-complexity.
In FOCS, pages 366-375, 2002.
[ doi ]
|
|
[1]
|
Sanjeev Arora.
Approximation schemes for geometric np-hard problems: A survey.
In FSTTCS, pages 16-17, 2001.
[ doi ]
|
|
[2]
|
Sanjeev Arora and Ravi Kannan.
Learning mixtures of arbitrary gaussians.
In STOC, pages 247-257, 2001.
[ doi ]
|
|
[3]
|
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
Salil P. Vadhan, and Ke Yang.
On the (im)possibility of obfuscating programs.
In CRYPTO, pages 1-18, 2001.
[ doi ]
|
|
[4]
|
Yair Bartal, Moses Charikar, and Danny Raz.
Approximating min-sum -clustering in metric spaces.
In STOC, pages 11-20, 2001.
[ doi ]
|
|
[5]
|
Amit Chakrabarti and Subhash Khot.
Improved lower bounds on the randomized complexity of graph
properties.
In ICALP, pages 285-296, 2001.
[ doi ]
|
|
[6]
|
Amit Chakrabarti, Subhash Khot, and Yaoyun Shi.
Evasiveness of subgraph containment and related properties.
In STACS, pages 110-120, 2001.
[ doi ]
|
|
[7]
|
Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao.
Informational complexity and the direct sum problem for simultaneous
message complexity.
In FOCS, pages 270-278, 2001.
|
|
[8]
|
Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan.
Algorithms for facility location problems with outliers.
In SODA, pages 642-651, 2001.
[ doi ]
|
|
[9]
|
Moses Charikar and Rina Panigrahy.
Clustering to minimize the sum of cluster diameters.
In STOC, pages 1-10, 2001.
[ doi ]
|
|
[10]
|
Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera
Sacristan, and Monique Teillaud.
Splitting a delaunay triangulation in linear time.
In ESA, pages 312-320, 2001.
[ doi ]
|
|
[11]
|
Bernard Chazelle and Ding Liu.
Lower bounds for intersection searching and fractional cascading in
higher dimension.
In STOC, pages 322-329, 2001.
[ doi ]
|
|
[12]
|
Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan.
Approximating the minimum spanning tree weight in sublinear time.
In ICALP, pages 190-200, 2001.
[ doi ]
|
|
[13]
|
Yevgeniy Dodis, Amit Sahai, and Adam Smith.
On perfect and adaptive security in exposure-resilient cryptography.
In EUROCRYPT, pages 301-324, 2001.
[ doi ]
|
|
[14]
|
Johan Håstad and Subhash Khot.
Query efficient pcps with perfect completeness.
In FOCS, pages 610-619, 2001.
|
|
[15]
|
Bill G. Horne, Lesley R. Matheson, Casey Sheehan, and Robert Endre Tarjan.
Dynamic self-checking techniques for improved tamper resistance.
In Digital Rights Management Workshop, pages 141-159, 2001.
[ doi ]
|
|
[16]
|
Peter Høyer, Jan Neerbek, and Yaoyun Shi.
Quantum complexities of ordered searching, sorting, and element
distinctness.
In ICALP, pages 346-357, 2001.
[ doi ]
|
|
[17]
|
Haim Kaplan, Robert Endre Tarjan, and Kostas Tsioutsiouliklis.
Faster kinetic heaps and their use in broadcast scheduling.
In SODA, pages 836-844, 2001.
[ doi ]
|
|
[18]
|
Subhash Khot.
Improved inaproximability results for maxclique, chromatic number and
approximate graph coloring.
In FOCS, pages 600-609, 2001.
|
|
[19]
|
Robert Osada, Thomas A. Funkhouser, Bernard Chazelle, and David P. Dobkin.
Matching 3d models with shape distributions.
In Shape Modeling International, pages 154-166, 2001.
[ doi ]
|
|
[20]
|
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano,
and Amit Sahai.
Robust non-interactive zero knowledge.
In CRYPTO, pages 566-598, 2001.
[ doi ]
|
|
[21]
|
Andrew Chi-Chih Yao.
Some perspective on computational complexity (abstract).
In STOC, page 600, 2001.
[ doi ]
|
|
[1]
|
Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, and Andrew Chi-Chih Yao.
Quantum bit escrow.
In STOC, pages 705-714, 2000.
[ doi ]
|
|
[2]
|
Sanjeev Arora.
Approximation algorithms that take advice.
In APPROX, page 1, 2000.
[ doi ]
|
|
[3]
|
Sanjeev Arora and George Karakostas.
A 2+epsilon approximation algorithm for the -mst problem.
In SODA, pages 754-759, 2000.
[ doi ]
|
|
[4]
|
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai.
Exposure-resilient functions and all-or-nothing transforms.
In EUROCRYPT, pages 453-469, 2000.
[ doi ]
|
|
[5]
|
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar
Raghavan, and Amit Sahai.
Query strategies for priced information (extended abstract).
In STOC, pages 582-591, 2000.
[ doi ]
|
|
[6]
|
Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, and Amit
Sahai.
Combinatorial feature selection problems.
In FOCS, pages 631-640, 2000.
|
|
[7]
|
Bernard Chazelle.
Irregularities of distribution, derandomization, and complexity
theory.
In FSTTCS, pages 46-54, 2000.
[ doi ]
|
|
[8]
|
Bernard Chazelle and Alexey Lvov.
A trace bound for the hereditary discrepancy.
In Symposium on Computational Geometry, pages 64-69, 2000.
[ doi ]
|
|
[9]
|
Venkatesan Guruswami, Amit Sahai, and Madhu Sudan.
"soft-decision" decoding of chinese remainder codes.
In FOCS, pages 159-168, 2000.
|
|
[10]
|
Subhash Khot and Venkatesh Raman.
Parameterized complexity of finding subgraphs with hereditary
properties.
In COCOON, pages 137-147, 2000.
[ doi ]
|
|
[11]
|
Hideyuki Mizuta and Kenneth Steiglitz.
Agent-based simulation of dynamic online auctions.
In Winter Simulation Conference, pages 1772-1777, 2000.
[ doi ]
|
|
[12]
|
Iannis Tourlakis.
Time-space lower bounds for sat on uniform and non-uniform machines.
In IEEE Conference on Computational Complexity, pages 22-,
2000.
[ doi ]
|