Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1074.68500].
Indexed articles:
Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel, Recognizing string graphs in NP, 1-6, electronic only [Zbl 1192.68376]
Chan, Timothy M., Dynamic subgraph connectivity with geometric applications, 7-13, electronic only [Zbl 1192.68172]
Eiter, Thomas; Gottlob, Georg; Makino, Kazuhisa, New results on monotone dualization and generating hypergraph transversals, 14-22, electronic only [Zbl 1192.68356]
Adleman, Len; Cheng, Qi; Goel, Ashish; Huang Ming-Deh; Kempe, David; Moisset de Espanés, Pablo; Rothemund, Paul Wilhelm Karl, Combinatorial optimization problems in self-assembly, 23-32, electronic only [Zbl 1192.90151]
Dinur, Irit; Safra, Shmuel, The importance of being biased, 33-42, electronic only [Zbl 1192.68318]
Håstad, Johan; Venkatesh, S., On the advantage over a random assignment, 43-52, electronic only [Zbl 1192.68902]
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike, The complexity of choosing an \(H\)-colouring (nearly) uniformly at random, 53-62, electronic only [Zbl 1192.68898]
Karger, David R.; Levine, Matthew S., Random sampling in residual graphs, 63-66, electronic only [Zbl 1192.90230]
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel, On the complexity of equilibria, 67-71, electronic only [Zbl 1192.91145]
Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R., Competitive generalized auctions, 72-81, electronic only [Zbl 1192.91103]
Drineas, Petros; Kerenidis, Iordanis; Raghavan Prabhakar, Competitive recommendation systems, 82-90, electronic only [Zbl 1192.91076]
Molloy, Michael, The Glauber dynamics on colourings of a graph with high girth and maximum degree, 91-98, electronic only [Zbl 1192.05055]
Gács, Peter, Clairvoyant scheduling of random walks, 99-108, electronic only [Zbl 1192.05158]
Bertsimas, Dimitris; Vempala, Santosh, Solving convex programs by random walks, 109-115, electronic only [Zbl 1192.90140]
Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep, Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths, 117-123 [Zbl 1192.68469]
Kontogiannis, Spyros, Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines, 124-133, electronic only [Zbl 1192.68277]
Albers, Susanne, On randomized online scheduling, 134-143, electronic only [Zbl 1192.68091]
Raz, Ran, On the complexity of matrix product, 144-151, electronic only [Zbl 1192.68327]
Gilbert, A. C.; Guha, S.; Indyk, P.; Muthukrishnan, S.; Strauss, M., Near-optimal sparse Fourier representations via sampling, 152-161, electronic only [Zbl 1192.94078]
Arora, Sanjeev; Khot, Subhash, Fitting algebraic curves to noisy data, 162-169, electronic only [Zbl 1192.68341]
Scharbrodt, Mark; Schickinger, Thomas; Steger, Angelika, A new average case analysis for completion time scheduling, 170-178, electronic only [Zbl 1192.90080]
Chan, Wun-Tat; Lam, Tak-Wah; Ting, Hing-Fung; Wong, Wai-Ha, A unified analysis of hot video schedulers, 179-188 [Zbl 1192.90066]
Srinivasan, Anand; Anderson, James H., Optimal rate-based scheduling on multiprocessors, 189-198, electronic only [Zbl 1192.68109]
Achlioptas, Dimitris; Moore, Cristopher, Almost all graphs with average degree 4 are 3-colorable, 199-208, electronic only [Zbl 1192.05042]
Molloy, Michael, Models and thresholds for random constraint satisfaction problems, 209-217, electronic only [Zbl 1192.68652]
Smyth, Clifford, Reimer’s inequality and Tardos’ conjecture, 218-221, electronic only [Zbl 1192.68379]
Chien, Steve; Rasmussen, Lars; Sinclair, Alistair, Clifford algebras and approximating the permanent, 222-231 [Zbl 1192.68885]
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek, Random sampling and approximation of MAX-CSP problems, 232-239, electronic only [Zbl 1192.68865]
Cryan, Mary; Dyer, Martin, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, 240-249, electronic only [Zbl 1192.68886]
Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr, Approximate clustering via core-sets, 250-257, electronic only [Zbl 1192.68871]
Albers, Susanne; Favrholdt, Lene M.; Giel, Oliver, On paging with locality of reference, 258-267, electronic only [Zbl 1192.68271]
Arge, Lars; Bender, Michael A.; Demaine, Erik D.; Holland-Minkley, Bryan; Munro, J. Ian, Cache-oblivious priority queue and graph algorithm applications, 268-276, electronic only [Zbl 1192.68166]
Bachmat, E., Average case analysis for batched disk scheduling and increasing subsequences, 277-286, electronic only [Zbl 1192.68940]
Czumaj, Artur; Krysta, Piotr; Vöcking, Berthold, Selfish traffic allocation for server farms, 287-296, electronic only [Zbl 1192.68033]
Chekuri, Chandra; Khanna, Sanjeev, Approximation schemes for preemptive weighted flow time, 297-305, electronic only [Zbl 1192.68877]
Cheriyan, Joseph; Vempala, Santosh; Vetta, Adrian, Approximation algorithms for minimum-cost \(k\)-vertex connected subgraphs, 306-312, electronic only [Zbl 1192.68883]
Jain, Kamal; Vazirani, Vijay V., Equitable cost allocations via primal-dual-type algorithms, 313-321, electronic only [Zbl 1192.90107]
Dwork, Cynthia; Stockmeyer, Larry, 2-round zero knowledge and proof auditors, 322-331, electronic only [Zbl 1192.68291]
Goldreich, Oded, Concurrent zero-knowledge with timing, revisited, 332-340, electronic only [Zbl 1192.68293]
Dziembowski, Stefan; Maurer, Ueli, Tight security proofs for the bounded-storage model, 341-350, electronic only [Zbl 1192.94094]
Khot, Subhash, Hardness results for approximate hypergraph coloring, 351-359, electronic only [Zbl 1192.68325]
Saks, Michael; Sun, Xiaodong, Space lower bounds for distance approximation in the data stream model, 360-369, electronic only [Zbl 1192.68331]
Ajtai, Miklós; Jayram, T. S.; Kumar, Ravi; Sivakumar, D., Approximate counting of inversions in a data stream, 370-379, electronic only [Zbl 1192.68455]
Charikar, Moses S., Similarity estimation techniques from rounding algorithms, 380-388, electronic only [Zbl 1192.68226]
Gilbert, Anna C.; Guha, Sudipto; Indyk, Piotr; Kotidis, Yannis; Muthukrishnan, S.; Strauss, Martin J., Fast, small-space algorithms for approximate histogram maintenance, 389-398, electronic only [Zbl 1192.68962]
Anshelevich, Elliot; Kempe, David; Kleinberg, Jon, Stability of load balancing algorithms in dynamic adversarial systems, 399-406, electronic only [Zbl 1192.68092]
Adler, Micah, Tradeoffs in probabilistic packet marking for IP traceback, 407-418, electronic only [Zbl 1192.68016]
Cooper, Colin; Frieze, Alan, Crawling on web graphs, 419-427, electronic only [Zbl 1192.68803]
Roughgarden, Tim, The price of anarchy is independent of the network topology, 428-437, electronic only [Zbl 1192.68054]
Elkin, Michael; Kortsarz, Guy, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, 438-447, electronic only [Zbl 1192.68891]
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair, An exponential separation between regular and general resolution, 448-456, electronic only [Zbl 1192.03039]
Ben-Sasson, Eli, Size space tradeoffs for resolution, 457-464, electronic only [Zbl 1192.03040]
Hellerstein, Lisa; Raghavan, Vijay, Exact learning of DNF formulas using DNF hypotheses, 465-473, electronic only [Zbl 1192.68389]
Fischer, Eldar; Lehman, Eric; Newman, Ilan; Raskhodnikova, Sofya; Rubinfeld, Ronitt; Samorodnitsky, Alex, Monotonicity testing over general poset domains, 474-483, electronic only [Zbl 1192.68359]
Barak, Boaz; Lindell, Yehuda, Strict polynomial-time in simulation and extraction, 484-493, electronic only [Zbl 1192.68343]
Canetti, Ran; Lindell, Yehuda; Ostrovsky, Rafail; Sahai, Amit, Universally composable two-party and multi-party secure computation, 494-503, electronic only [Zbl 1192.94112]
Ajtai, Miklós, The invasiveness of off-line memory checking, 504-513, electronic only [Zbl 1192.68225]
Lindell, Yehuda; Lysyanskaya, Anna; Rabin, Tal, On the composition of authenticated byzantine agreement, 514-523, electronic only [Zbl 1192.68084]
Aspnes, James; Shah, Gauri; Shah, Jatin, Wait-free consensus with infinite arrivals, 524-533, electronic only [Zbl 1192.68850]
Feige, Uriel, Relations between average case complexity and approximation complexity, 534-543, electronic only [Zbl 1192.68358]
Holmerin, Jonas, Vertex cover on 4-regular hyper-graphs is hard to approximate within \(2-\epsilon\), 544-552, electronic only [Zbl 1192.68323]
Raz, Ran, Resolution lower bounds for the weak pigeonhole principle, 553-562, electronic only [Zbl 1192.03043]
Ben-Sasson, Eli, Hard examples for bounded depth frege, 563-572, electronic only [Zbl 1192.03041]
Kaplan, Haim; Shafrir, Nira; Tarjan, Robert E., Meldable heaps and Boolean union-find, 573-582, electronic only [Zbl 1192.68181]
Brodal, Gerth Stølting; Lagogiannis, George; Makris, Christos; Tsakalidis, Athanasios; Tsichlas, Kostas, Optimal finger search trees in the pointer machine, 583-591, electronic only [Zbl 1192.68170]
Cole, Richard; Hariharan, Ramesh, Verifying candidate matches in sparse and wildcard matching, 592-601 [Zbl 1192.68819]
Han, Yijie, Deterministic sorting in \(O(n\log\log n)\) time and linear space, 602-608, electronic only [Zbl 1192.68196]
Micciancio, Daniele, Improved cryptographic hash functions with worst-case/average-case connection, 609-618, electronic only [Zbl 1192.94103]
Sivakumar, D., Algorithmic derandomization via complexity theory, 619-626, electronic only [Zbl 1192.68303]
Umans, Christopher, Pseudo-random generators for all hardnesses, 627-634, electronic only [Zbl 1192.68863]
Aaronson, Scott, Quantum lower bound for the collision problem, 635-642, electronic only [Zbl 1192.68255]
Crépeau, Claude; Gottesman, Daniel; Smith, Adam, Secure multi-party quantum computation, 643-652, electronic only [Zbl 1192.94115]
Hallgren, Sean, Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem, 653-658, electronic only [Zbl 1192.81069]
Capalbo, Michael; Reingold, Omer; Vadhan, Salil; Wigderson, Avi, Randomness conductors and constant-degree lossless expanders, 659-668, electronic only [Zbl 1192.68475]
Meshulam, Roy; Wigderson, Avi, Expanders from symmetric codes, 669-677, electronic only [Zbl 1192.68463]
Batu, Tuǧkan; Dasgupta, Sanjoy; Kumar, Ravi; Rubinfeld, Ronitt, The complexity of approximating entropy, 678-687, electronic only [Zbl 1192.94074]
Beame, Paul; Vee, Erik, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, 688-697, electronic only [Zbl 1192.68346]
Nayak, Ashwin; Salzman, Julia, On communication over an entanglement-assisted quantum channel, 698-704, electronic only [Zbl 1192.81095]
Linial, Nathan; Magen, Avner; Naor, Assaf, Girth and Euclidean distortion, 705-711, electronic only [Zbl 1192.05040]
Basu, Saugata, Computing the Betti numbers of arrangements, 712-720, electronic only [Zbl 1192.14043]
Arya, Sunil; Malamatos, Theocharis; Mount, David M., Space-efficient approximate Voronoi diagrams, 721-730, electronic only [Zbl 1192.68727]
Jain, Kamal; Mahdian, Mohammad; Saberi, Amin, A new greedy approach for facility location problems, 731-740, electronic only [Zbl 1192.90106]
Karger, David R.; Ruhl, Matthias, Finding nearest neighbors in growth-restricted metrics, 741-750, electronic only [Zbl 1192.68750]
O’Donnell, Ryan, Hardness amplification within NP, 751-760, electronic only [Zbl 1192.68300]
Agol, Ian; Hass, Joel; Thurston, William, 3-manifold knot genus is NP-complete, 761-766, electronic only [Zbl 1192.68305]
Khot, Subhash, On the power of unique 2-prover 1-round games, 767-775, electronic only [Zbl 1192.68367]
Jackson, Jeffrey C.; Klivans, Adam R.; Servedio, Rocco A., Learnability beyond \(\mathrm{AC}^0\), 776-784, electronic only [Zbl 1192.68390]
Golin, Mordecai J.; Kenyon, Claire; Young, Neal E., Huffman coding with unequal letter costs, 785-791, electronic only [Zbl 1192.68899]
Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, April; Sahai, Amit; Shelat, Abhi, Approximating the smallest grammar: Kolmogorov complexity in natural models, 792-801, electronic only [Zbl 1192.68397]
Guruswami, Venkatesan, Limits to list decodability of linear codes, 802-811, electronic only [Zbl 1192.94125]
Guruswami, Venkatesan; Indyk, Piotr, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets, 812-821, electronic only [Zbl 1192.94132]
Papadimitriou, Christos H., The joy of theory, 116, electronic only [Zbl 1192.68253]