×

zbMATH — the first resource for mathematics

Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. (English) Zbl 1194.68005
Lecture Notes in Computer Science 6198. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). xxiii, 754 p. (2010).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding colloquium has been reviewed (see Zbl 1166.68001 and Zbl 1166.68002). For the second part of the proceedings of the present colloquium see Zbl 1194.68006.
Indexed articles:
Monien, Burkhard; Dumrauf, Dominic; Tscheuschner, Tobias, Local search: simple, successful, but sometimes sluggish, 1-17 [Zbl 1287.68157]
Bonichon, Nicolas; Gavoille, Cyril; Hanusse, Nicolas; Perković, Ljubomir, Plane spanners of maximum degree six, 19-30 [Zbl 1287.68168]
Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank, The positive semidefinite Grothendieck problem with rank constraint, 31-42 [Zbl 1287.68178]
Amir, Amihood; Eisenberg, Estrella; Levy, Avivit; Porat, Ely; Shapira, Natalie, Cycle detection and correction, 43-54 [Zbl 1287.68187]
Král’, Daniel, Decomposition width of matroids, 55-66 [Zbl 1287.68144]
Bateni, MohammadHossein; Hajiaghayi, MohammadTaghi; Immorlica, Nicole; Mahini, Hamid, The cooperative game theory foundations of network bargaining games, 67-78 [Zbl 1287.91008]
Harks, Tobias; Klimm, Max, On the existence of pure Nash equilibria in weighted congestion games, 79-89 [Zbl 1287.91005]
Borodin, Allan; Lucier, Brendan, On the limitations of greedy mechanism design for truthful combinatorial auctions, 90-101 [Zbl 1287.91082]
Atserias, Albert; Maneva, Elitza, Mean-payoff games and propositional proofs, 102-113 [Zbl 1287.03101]
Anagnostopoulos, Aris; Grandoni, Fabrizio; Leonardi, Stefano; Sankowski, Piotr, Online network design with outliers, 114-126 [Zbl 1287.68012]
Libert, Benoît; Yung, Moti, Efficient completely non-malleable public key encryption, 127-139 [Zbl 1287.94082]
Ito, Tsuyoshi, Polynomial-space approximation of no-signaling provers, 140-151 [Zbl 1287.68051]
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal, From secrecy to soundness: efficient verification via secure computation (extended abstract), 152-163 [Zbl 1287.68041]
Iacono, John; Özkan, Özgür, Mergeable dictionaries, 164-175 [Zbl 1287.68030]
Fakcharoenphol, Jittat; Laekhanukit, Bundit; Nanongkai, Danupon, Faster algorithms for semi-matching problems (extended abstract), 176-187 [Zbl 1287.05148]
Li, Jian; Yi, Ke; Zhang, Qin, Clustering with diversity, 188-200 [Zbl 1287.68182]
Duan, Ran, New data structures for subgraph connectivity, 201-212 [Zbl 1287.68028]
Dietzfelbinger, Martin; Goerdt, Andreas; Mitzenmacher, Michael; Montanari, Andrea; Pagh, Rasmus; Rink, Michael, Tight thresholds for Cuckoo hashing via XORSAT (extended abstract), 213-225 [Zbl 1256.68047]
Cole, Richard; Ramachandran, Vijaya, Resource oblivious sorting on multicores, 226-237 [Zbl 1287.68032]
Jiménez, Rosa M.; Martínez, Conrado, Interval sorting, 238-249 [Zbl 1287.68033]
Bansal, Nikhil; Khot, Subhash, Inapproximability of hypergraph vertex cover and applications to scheduling problems, 250-261 [Zbl 1287.90018]
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R., Thresholded covering algorithms for robust and max-min optimization, 262-274 [Zbl 1287.68180]
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan, Graph homomorphisms with complex values: a dichotomy theorem (extended abstract), 275-286 [Zbl 1288.05178]
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi), Metrical task systems and the \(k\)-server problem on HSTs, 287-298 [Zbl 1288.68282]
Eisenbrand, Friedrich; Hähnle, Nicolai; Niemeier, Martin; Skutella, Martin; Verschae, José; Wiese, Andreas, Scheduling periodic tasks in a hard real-time environment, 299-311 [Zbl 1288.90026]
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk, Scalably scheduling power-heterogeneous processors, 312-323 [Zbl 1288.68033]
Bansal, Nikhil; Krishnaswamy, Ravishankar; Nagarajan, Viswanath, Better scalable algorithms for broadcast scheduling, 324-335 [Zbl 1288.68284]
Epstein, Leah; Levin, Asaf; van Stee, Rob, Max-min online allocations with a reordering buffer, 336-347 [Zbl 1288.90027]
Fountoulakis, Nikolaos; Panagiotou, Konstantinos, Orientability of random hypergraphs and the power of multiple choices, 348-359 [Zbl 1288.05186]
Guruswami, Venkatesan; Saket, Rishi, On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs, 360-371 [Zbl 1288.68093]
Rué, Juanjo; Sau, Ignasi; Thilikos, Dimitrios M., Dynamic programming for graphs on surfaces, 372-383 [Zbl 1288.05286]
Köbler, Johannes; Kuhnert, Sebastian; Laubner, Bastian; Verbitsky, Oleg, Interval graphs: canonical representation in logspace, 384-395 [Zbl 1288.05281]
Goldberg, Leslie Ann; Jerrum, Mark, Approximating the partition function of the ferromagnetic Potts model, 396-407 [Zbl 1288.68091]
Shpilka, Amir; Volkovich, Ilya, On the relation between polynomial identity testing and finding variable disjoint factors, 408-419 [Zbl 1288.68252]
Litow, B., On sums of roots of unity, 420-425 [Zbl 1288.68251]
Dell, Holger; Husfeldt, Thore; Wahlén, Martin, Exponential time complexity of the permanent and the Tutte polynomial (extended abstract), 426-437 [Zbl 1288.68111]
Bhattacharya, Amitava; DasGupta, Bhaskar; Mubayi, Dhruv; Turán, György, On approximate Horn formula minimization, 438-450 [Zbl 1288.68086]
Beimel, Amos; Ben Daniel, Sebastian; Kushilevitz, Eyal; Weinreb, Enav, Choosing, agreeing, and eliminating in communication complexity, 451-462 [Zbl 1288.68064]
Woodruff, David P., Additive spanners in nearly quadratic time, 463-474 [Zbl 1288.68190]
Lee, Troy; Zhang, Shengyu, Composition theorems in communication complexity, 475-489 [Zbl 1288.68065]
Grandoni, Fabrizio; Rothvoß, Thomas, Network design via core detouring for problems without a core, 490-502 [Zbl 1288.68013]
Ambos-Spies, Klaus; Bakibayev, Timur, Weak completeness notions for exponential time, 503-514 [Zbl 1288.68077]
Bojańczyk, Mikołaj; Parys, Paweł, Efficient evaluation of nondeterministic automata using factorization forests, 515-526 [Zbl 1288.68147]
Jacobs, Tobias; Cicalese, Ferdinando; Laber, Eduardo; Molinaro, Marco, On the complexity of searching in trees: average-case minimization, 527-539 [Zbl 1288.68125]
Krovi, Hari; Magniez, Frédéric; Ozols, Maris; Roland, Jérémie, Finding is as easy as detecting for quantum walks, 540-551 [Zbl 1288.68072]
Cheraghchi, Mahdi, Improved constructions for non-adaptive threshold group testing, 552-564 [Zbl 1288.68107]
Rubinfeld, Ronitt; Xie, Ning, Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract), 565-581 [Zbl 1288.68136]
Gamzu, Iftah; Segev, Danny, A sublogarithmic approximation for highway and tollbooth pricing, 582-593 [Zbl 1288.68265]
Makarychev, Konstantin; Manokaran, Rajsekar; Sviridenko, Maxim, Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm, 594-604 [Zbl 1288.68273]
Greve, Mark; Jørgensen, Allan Grønlund; Larsen, Kasper Dalgaard; Truelsen, Jakob, Cell probe lower bounds and approximations for range mode, 605-616 [Zbl 1288.68046]
Guruswami, Venkatesan; Khot, Subhash; O’Donnell, Ryan; Popat, Preyas; Tulsiani, Madhur; Wu, Yi, SDP gaps for 2-to-1 and other Label-Cover variants, 617-628 [Zbl 1288.68092]
Rudra, Atri; Uurtamo, Steve, Data stream algorithms for codeword testing (extended abstract), 629-640 [Zbl 1288.68063]
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario, Streaming algorithms for independent sets, 641-652 [Zbl 1288.68189]
Kratsch, Stefan; Wahlström, Magnus, Preprocessing of min ones problems: a dichotomy, 653-665 [Zbl 1288.68132]
Xia, Mingji, Holographic reduction: a domain changed application and its partial converse theorems, 666-677 [Zbl 1288.68139]
Grossi, Roberto; Orlandi, Alessio; Raman, Rajeev, Optimal trade-offs for succinct string indexes, 678-689 [Zbl 1288.68047]
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R., Approximation algorithms for optimal decision trees and adaptive TSP problems, 690-701 [Zbl 1288.68267]
Yao, Andrew C.; Yung, Moti; Zhao, Yunlei, Concurrent knowledge extraction in the public-key model, 702-714 [Zbl 1288.94086]
Pǎtraşcu, Mihai; Thorup, Mikkel, On the \(k\)-independence required by linear probing and minwise independence, 715-726 [Zbl 1288.68050]
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko, Covering and packing in linear space, 727-737 [Zbl 1288.68102]
Georgiadis, Loukas, Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs, 738-749 [Zbl 1288.05273]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Nxx Theory of software
68Qxx Theory of computing
00B25 Proceedings of conferences of miscellaneous specific interest
PDF BibTeX XML Cite
Full Text: DOI