Show indexed articles as search result.

The articles of this volume will be reviewed individually.
Indexed articles:
Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B., A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract), 1-10 [Zbl 1346.68253]
Wayne, Kevin D., A polynomial combinatorial algorithm for generalized minimum cost flow, 11-18 [Zbl 1345.90103]
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, 19-28 [Zbl 1346.68102]
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel, PCP characterizations of NP: towards a polynomially-small error-probability, 29-40 [Zbl 1346.68096]
Ergün, Funda; Kumar, Ravi; Rubinfeld, Ronitt, Fast approximate PCPs, 41-50 [Zbl 1346.68097]
Kiwi, Marcos; Magniez, Frédéric; Santha, Miklos, Approximate testing with relative error, 51-60 [Zbl 1345.65027]
Zwick, Uri, All pairs lightest shortest paths, 61-69 [Zbl 1345.05106]
Gabow, Harold N.; Kaplan, Haim; Tarjan, Robert E., Unique maximum matching algorithms, 70-78 [Zbl 1345.05100]
Ishai, Yuval; Kushilevitz, Eyal, Improved upper bounds on information-theoretic private information retrieval (extended abstract), 79-88 [Zbl 1346.68083]
Beimel, Amos; Ishai, Yuval; Kushilevitz, Eyal; Malkin, Tal, One-way functions are essential for single-server private information retrieval, 89-98 [Zbl 1346.68081]
Charikar, Moses; Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew, On targeting Markov segments, 99-108 [Zbl 1345.90104]
Cohen, Edith; Kaplan, Haim, Exploiting regularities in web traffic patterns for cache replacement, 109-118 [Zbl 1346.68030]
Chen, Gen-Huey; Kao, Ming-Yang; Lyuu, Yuh-Dauh; Wong, Hsing-Kuo, Optimal buy-and-hold strategies for financial markets with bounded daily returns, 119-128 [Zbl 1345.91010]
Nisan, Noam; Ronen, Amir, Algorithmic mechanism design (extended abstract), 129-140 [Zbl 1346.68246]
Trevisan, Luca, Construction of extractors using pseudo-random generators (extended abstract), 141-148 [Zbl 1345.68239]
Raz, Ran; Reingold, Omer; Vadhan, Salil, Extracting all the randomness and reducing the error in Trevisan’s extractors, 149-158 [Zbl 1345.68136]
Raz, Ran; Reingold, Omer, On recycling the randomness of states in space bounded computation, 159-168 [Zbl 1345.68135]
Di Crescenzo, Giovanni; Impagliazzo, Russell, Security-preserving hardness-amplification for any regular one-way function, 169-178 [Zbl 1345.94056]
Edmonds, Jeff, Scheduling in the dark, 179-188 [Zbl 1345.68028]
Goel, Ashish; Henzinger, Monika R.; Plotkin, Serge; Tardos, Eva, Scheduling data transfers in a network and the set scheduling problem, 189-197 [Zbl 1345.68030]
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded, Minimizing the flow time without migration, 198-205 [Zbl 1345.68025]
Gamarnik, David, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, 206-214 [Zbl 1345.90040]
Scheideler, Christian; Vöcking, Berthold, From static to dynamic routing: efficient transformations of store-and-forward protocols, 215-224 [Zbl 1345.68031]
Goldreich, Oded; Ron, Dana; Sudan, Madhu, Chinese remaindering with errors, 225-234 [Zbl 1345.94105]
Olshevsky, Vadim; Shokrollahi, M. Amin, A displacement approach to efficient decoding of algebraic-geometric codes, 235-244 [Zbl 1345.94104]
Naor, Moni; Pinkas, Benny, Oblivious transfer and polynomial evaluation, 245-254 [Zbl 1345.68018]
Canetti, Ran; Ostrovsky, Rafail, Secure computation with honest-looking parties: what if nobody is truly honest? (extended abstract), 255-264 [Zbl 1345.68017]
Dinitz, Yefim; Moran, Shlomo; Rajsbaum, Sergio, Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract), 265-274 [Zbl 1345.68014]
Chen, Fang; Lovász, László; Pak, Igor, Lifting Markov chains to speed up mixing, 275-281 [Zbl 1345.60075]
Lovász, László; Kannan, Ravi, Faster mixing via average conductance, 282-287 [Zbl 1345.60078]
Schulman, Leonard J.; Vazirani, Vijay V., Majorizing estimators and the approximation of #P-complete problems, 288-294 [Zbl 1346.68114]
Beame, Paul; Fich, Faith E., Optimal bounds for the predecessor problem, 295-304 [Zbl 1346.68099]
Chakrabarti, Amit; Chazelle, Bernard; Gum, Benjamin; Lvov, Alexey, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, 305-311 [Zbl 1346.68078]
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval, Lower bounds for high dimensional nearest neighbor search and related problems, 312-321 [Zbl 1346.68077]
Schulman, Leonard J.; Vazirani, Umesh V., Molecular scale heat engines and scalable quantum computation, 322-329 [Zbl 1345.81028]
Hales, Lisa; Hallgren, Sean, Quantum Fourier sampling simplified, 330-338 [Zbl 1345.68140]
Russell, Alexander; Saks, Michael; Zuckerman, David, Lower bounds for leader election and collective coin-flipping in the perfect information model, 339-347 [Zbl 1345.68020]
Gál, Anna; Rosén, Adi, A theorem on sensitivity and applications in private computation, 348-357 [Zbl 1345.94061]
Raz, Ran, Exponential separation of quantum and classical communication complexity, 358-367 [Zbl 1345.68134]
Amano, Masami; Iwama, Kazuo, Undecidability on quantum finite automata, 368-375 [Zbl 1346.68090]
Ambainis, Andris; Nayak, Ashwin; Ta-Shma, Ammon; Vazirani, Umesh, Dense quantum coding and a lower bound for 1-way quantum automata, 376-383 [Zbl 1345.68195]
Nayak, Ashwin; Wu, Felix, The quantum query complexity of approximating the median and related statistics, 384-393 [Zbl 1345.68141]
Jansen, Klaus; Solis-Oba, Roberto; Sviridenko, Maxim, Makespan minimization in job shops: a polynomial time approximation scheme, 394-399 [Zbl 1345.90044]
Skutella, Martin; Woeginger, Gerhard J., A PTAS for minimizing the weighted sum of job completion times on parallel machines, 400-407 [Zbl 1345.90045]
Jansen, Klaus; Porkolab, Lorant, Improved approximation schemes for scheduling unrelated parallel machines, 408-417 [Zbl 1345.90043]
Chen, Jianer; Miranda, Antonio, A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract), 418-427 [Zbl 1345.68027]
Indyk, Piotr, Sublinear time algorithms for metric space problems, 428-434 [Zbl 1346.68256]
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval, Subquadratic approximation algorithms for clustering problems in high dimensional spaces, 435-444 [Zbl 1345.62088]
Anil Kumar, V. S.; Ramesh, H., Covering rectilinear polygons with axis-parallel rectangles, 445-454 [Zbl 1346.68228]
Muthukrishnan, S.; Paterson, Mike; Sahinalp, Süleyman Cenk; Suel, Torsten, Compact grid layouts of multi-level networks, 455-463 [Zbl 1345.68015]
Feder, Tomas; Hell, Pavol; Klein, Sulamita; Motwani, Rajeev, Complexity of graph partition problems, 464-472 [Zbl 1345.68171]
Li, Ming; Ma, Bin; Wang, Lusheng, Finding similar regions in many strings, 473-482 [Zbl 1346.68307]
Ferragina, Paolo; Muthukrishnan, S.; de Berg, Mark, Multi-method dispatching: a geometric approach with applications to string matching problems, 483-491 [Zbl 1345.68103]
King, Valerie; Sagert, Garry, A fully dynamic algorithm for maintaining the transitive closure, 492-498 [Zbl 1345.05102]
Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis, Worst-case and amortised optimality in union-find (extended abstract), 499-506 [Zbl 1346.68247]
Pan, Victor Y.; Chen, Zhao Q., The complexity of the matrix eigenproblem, 507-516 [Zbl 1346.68103]
Ben-Sasson, Eli; Wigderson, Avi, Short proofs are narrow – resolution made simple, 517-526 [Zbl 1346.68173]
Rojas, J. Maurice, On the complexity of Diophantine geometry in low dimensions (extended abstract), 527-536 [Zbl 1345.68181]
Sudan, Madhu; Trevisan, Luca; Vadhan, Salil, Pseudorandom generators without the XOR lemma (extended abstract), 537-546 [Zbl 1345.68138]
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann, Linear gaps between degrees for the polynomial calculus modulo distinct primes, 547-556 [Zbl 1345.03105]
Andrews, Matthew; Zhang, Lisa, Packet routing with arbitrary end-to-end delay requirements, 557-565 [Zbl 1345.68024]
Pandurangan, Gopal; Upfal, Eli, Static and dynamic evaluation of QoS properties, 566-573 [Zbl 1345.68019]
Guha, Sudipto; Moss, Anna; Naor, Joseph (Seffi); Schieber, Baruch, Efficient recovery from power outage (extended abstract), 574-582 [Zbl 1345.90042]
Feige, Uriel, Nonmonotonic phenomena in packet routing, 583-591 [Zbl 1345.68029]
Schaefer, Marcus, Graph Ramsey theory and the polynomial hierarchy, 592-601 [Zbl 1345.68147]
Ponzio, Stephen J.; Radhakrishnan, Jaikumar; Venkatesh, S., The communication complexity of pointer chasing: applications of entropy and sampling, 602-611 [Zbl 1345.68133]
Cohen, Edith; Kaplan, Haim; Zwick, Uri, Connection caching, 612-621 [Zbl 1345.68013]
Bar-Noy, Amotz; Guha, Sudipto; Naor, Joseph (Seffi); Schieber, Baruch, Approximating the throughput of multiple machines under real-time scheduling, 622-631 [Zbl 1345.68026]
Ajtai, Miklós, Determinism versus non-determinism for linear time RAMs (extended abstract), 632-641 [Zbl 1346.68093]
Valiant, Leslie G., Robust logics, 642-651 [Zbl 1346.68165]
Luks, Eugene M., Hypergraph isomorphism and structural equivalence of Boolean functions, 652-658 [Zbl 1345.68176]
Klivans, Adam R.; van Melkebeek, Dieter, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, 659-667 [Zbl 1345.68174]
Karger, David R.; Klein, Philip; Stein, Cliff; Thorup, Mikkel; Young, Neal E., Rounding algorithms for a geometric embedding of minimum multiway cut, 668-678 [Zbl 1345.90095]
Zwick, Uri, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems, 679-687 [Zbl 1345.90064]
Arora, Sanjeev; Karakostas, George, Approximation schemes for minimum latency problems, 688-693 [Zbl 1345.90110]
Gupta, Anupam, Embedding tree metrics into low dimensional Euclidean spaces, 694-700 [Zbl 1345.05065]
Servedio, Rocco A., Computational sample complexity and attribute-efficient learning, 701-710 [Zbl 1346.68116]
Blömer, Johannes; Seifert, Jean-Pierre, On the complexity of computing short linearly independent vectors and short bases in a lattice, 711-720 [Zbl 1345.11090]
Plandowski, Wojciech, Satisfiability of word equations with constants is in NEXPTIME, 721-725 [Zbl 1346.68113]
Cai, Jin-Yi; Nerurkar, Ajay; Sivakumar, D., Hardness and hierarchy theorems for probabilistic quasi-polynomial time, 726-735 [Zbl 1346.68095]
Indyk, Piotr, Interpolation of symmetric functions and a new type of combinatorial design, 736-740 [Zbl 1345.68268]
Capalbo, M. R.; Kosaraju, S. R., Small universal graphs, 741-749 [Zbl 1345.05097]
Dodis, Yevgeniy; Khanna, Sanjeev, Design networks with bounded pairwise distance, 750-759 [Zbl 1345.90032]
Schaeffer, Gilles, Random sampling of large planar maps and convex polyhedra, 760-769 [Zbl 1345.05105]
Kapoor, Sanjiv, Efficient computation of geodesic shortest paths, 770-779 [Zbl 1345.68263]
Ben-Amram, Amir M.; Petersen, Holger, Backing up in singly linked lists, 780-786 [Zbl 1346.68072]