zbMATH — the first resource for mathematics

Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. (English) Zbl 1217.68003
Lecture Notes in Computer Science 6755. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). xxv, 802 p. (2011).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding colloquium see Zbl 1194.68005 and 1194.68006. For Part II of the present colloquium see Zbl 1217.68004.
Indexed articles:
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory, Improved approximation for the directed spanner problem, 1-12 [Zbl 1332.68283]
Laekhanukit, Bundit, An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract), 13-24 [Zbl 1332.68287]
Adamaszek, Anna; Czumaj, Artur; Lingas, Andrzej; Wojtaszczyk, Jakub Onufry, Approximation schemes for capacitated geometric network design, 25-36 [Zbl 1332.68282]
Qian, Jiawei; Williamson, David P., An \(O(\log n)\)-competitive algorithm for online constrained forest problems, 37-48 [Zbl 1332.68296]
Zhang, Shengyu, On the power of lower bound methods for one-way quantum communication complexity, 49-60 [Zbl 1332.68054]
Aaronson, Scott; Drucker, Andrew, Advice coins for classical and quantum computation, 61-72 [Zbl 1332.68052]
Chailloux, André; Kerenidis, Iordanis; Rosgen, Bill, Quantum commitments from complexity assumptions, 73-85 [Zbl 1332.68053]
Harrow, Aram W.; Montanaro, Ashley; Short, Anthony J., Limitations on quantum dimensionality reduction, 86-97 [Zbl 1333.81072]
Canzar, Stefan; Elbassioni, Khaled; Klau, Gunnar W.; Mestre, Julián, On tree-constrained matchings and generalizations, 98-109 [Zbl 1332.68057]
Adler, Isolde; Kolliopoulos, Stavros G.; Krause, Philipp Klaus; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios, Tight bounds for linkages in planar graphs, 110-121 [Zbl 1333.05280]
Chimani, Markus; Hliněný, Petr, A tighter insertion-based approximation of the crossing number, 122-134 [Zbl 1332.68284]
Kawarabayashi, Ken-ichi; Klein, Philip N.; Sommer, Christian, Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs, 135-146 [Zbl 1332.68033]
Boros, Endre; Elbassioni, Khaled; Fouz, Mahmoud; Gurvich, Vladimir; Makino, Kazuhisa; Manthey, Bodo, Stochastic mean payoff games: smoothed analysis and approximation schemes, 147-158 [Zbl 1332.68064]
Dyer, Martin; Mohanaraj, Velumailum, Pairwise-interaction games, 159-170 [Zbl 1332.68071]
Elsässer, Robert; Tscheuschner, Tobias, Settling the complexity of local max-cut (almost) completely, 171-182 [Zbl 1332.68072]
Nonner, Tim, Clique clustering yields a PTAS for max-coloring interval graphs, 183-194 [Zbl 1332.68090]
Epstein, Leah; Imreh, Csanád; Levin, Asaf; Nagy-György, Judit, On variants of file caching, 195-206 [Zbl 1332.68044]
Böckenhauer, Hans-Joachim; Komm, Dennis; Královič, Rastislav; Královič, Richard, On the advice complexity of the \(k\)-server problem, 207-218 [Zbl 1332.68291]
Chan, Sze-Hang; Lam, Tak-Wah; Lee, Lap-Kei; Liu, Chi-Man; Ting, Hing-Fung, Sleep management on multiple machines for energy and flow time, 219-231 [Zbl 1332.68292]
Anand, S.; Garg, Naveen; Megow, Nicole, Meeting deadlines: how much speed suffices?, 232-243 [Zbl 1332.68019]
Durocher, Stephane; He, Meng; Munro, J. Ian; Nicholson, Patrick K.; Skala, Matthew, Range majority in constant time and linear space, 244-255 [Zbl 1332.68032]
Brodal, Gerth Stølting; Tsakalidis, Konstantinos, Dynamic planar range maxima queries, 256-267 [Zbl 1332.68031]
Farzan, Arash; Kamali, Shahin, Compact navigation and distance oracles for graphs with small treewidth, 268-280 [Zbl 1332.68170]
Hirt, Martin; Zikas, Vassilis, Player-centric Byzantine agreement, 281-292 [Zbl 1332.68010]
Allender, Eric; Friedman, Luke; Gasarch, William, Limits on the computational power of random strings, 293-304 [Zbl 1332.68095]
Coja-Oghlan, Amin; Pachon-Pinzon, Angelica Y., The decimation process in random \(k\)-SAT, 305-316 [Zbl 1332.68069]
Magniez, Frédéric; Nayak, Ashwin; Santha, Miklos; Xiao, David, Improved bounds for the randomized decision tree complexity of recursive majority, 317-329 [Zbl 1332.68085]
O’Donnell, Ryan; Wright, John; Zhou, Yuan, The Fourier entropy-influence conjecture for certain classes of Boolean functions, 330-341 [Zbl 1323.94189]
Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy, Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract), 342-353 [Zbl 1332.68285]
Chekuri, Chandra; Ene, Alina, Submodular cost allocation problem and applications, 354-366 [Zbl 1333.90092]
Kakimura, Naonori; Makino, Kazuhisa, Robust independence systems, 367-378 [Zbl 1333.05304]
Badanidiyuru Varadaraja, Ashwinkumar, Buyback problem – approximate matroid intersection with cancellation costs, 379-390 [Zbl 1333.91014]
Faust, Sebastian; Pietrzak, Krzysztof; Venturi, Daniele, Tamper-proof circuits: how to trade leakage for tamper-resilience, 391-402 [Zbl 1333.94034]
Arora, Sanjeev; Ge, Rong, New algorithms for learning in presence of errors, 403-415 [Zbl 1332.68099]
Harkins, Ryan C.; Hitchcock, John M., Exact learning algorithms, betting games, and circuit lower bounds, 416-423 [Zbl 1332.68100]
Bulatov, Andrei A.; Marx, Dániel, Constraint satisfaction parameterized by solution size, 424-436 [Zbl 1333.68136]
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan, Preprocessing for treewidth: a combinatorial analysis through kernelization, 437-448 [Zbl 1333.68204]
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry, Subset feedback vertex set is fixed-parameter tractable, 449-461 [Zbl 1334.68096]
Hermelin, Danny; Mnich, Matthias; van Leeuwen, Erik Jan; Woeginger, Gerhard J., Domination when the stars are out, 462-473 [Zbl 1334.68160]
Austrin, Per; Khot, Subhash, A simple deterministic reduction for the gap minimum distance of code problem, 474-485 [Zbl 1334.68082]
Feige, Uriel; Reichman, Daniel, Recoverable values for independent sets, 486-497 [Zbl 1334.68087]
Kuhn, Fabian; Mastrolilli, Monaldo, Vertex cover in graphs with locally few colors, 498-509 [Zbl 1334.68089]
Makarychev, Konstantin; Sviridenko, Maxim, Maximizing polynomials subject to assignment constraints, 510-520 [Zbl 1334.68302]
Goldberg, Leslie Ann; Jerrum, Mark, A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid, 521-532 [Zbl 1333.68122]
Bordewich, Magnus; Kang, Ross J., Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width, 533-544 [Zbl 1333.68288]
Chakraborty, Sourav; García-Soriano, David; Matsliah, Arie, Efficient sample extractors for juntas with applications, 545-556 [Zbl 1334.68297]
Ngo, Hung Q.; Porat, Ely; Rudra, Atri, Efficiently decodable error-correcting list disjunct matrices and applications (extended abstract), 557-568 [Zbl 1334.68298]
Fortnow, Lance; Santhanam, Rahul, Robust simulations and significant separations, 569-580 [Zbl 1333.68118]
Drucker, Andrew, A PCP characterization of AM, 581-592 [Zbl 1333.68117]
Clifford, Raphaël; Jalsenius, Markus, Lower bounds for online integer multiplication and convolution in the cell-probe model, 593-604 [Zbl 1333.68121]
Huang, Lei; Pitassi, Toniann, Automatizability and simple stochastic games, 605-617 [Zbl 1334.68100]
Filmus, Yuval; Pitassi, Toniann; Santhanam, Rahul, Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds, 618-629 [Zbl 1280.03055]
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander, Parameterized bounded-depth Frege is not optimal, 630-641 [Zbl 1334.03056]
Nordström, Jakob; Razborov, Alexander, On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution, 642-653 [Zbl 1334.03057]
Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena, Sorting by transpositions is difficult, 654-665 [Zbl 1334.68085]
Huang, Chien-Chung; Kavitha, Telikepalli, Popular matchings in the stable marriage problem, 666-677 [Zbl 1334.05168]
Cheng, Christine; McDermid, Eric; Suzuki, Ichiro, Center stable matchings and centers of cover graphs of distributive lattices, 678-689 [Zbl 1334.05114]
Abraham, Ittai; Delling, Daniel; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F., VC-dimension and shortest path algorithms, 690-699 [Zbl 1334.05161]
Mengel, Stefan, Characterizing arithmetic circuit classes by constraint satisfaction problems (extended abstract), 700-711 [Zbl 1333.68119]
Guo, Heng; Lu, Pinyan; Valiant, Leslie G., The complexity of symmetric Boolean parity Holant problems (extended abstract), 712-723 [Zbl 1333.68144]
Jansen, Maurice; Santhanam, Rahul, Permanent does not have succinct polynomial size arithmetic circuits of constant depth, 724-735 [Zbl 1333.68123]
Allender, Eric; Wang, Fengming, On the power of algebraic branching programs of width two, 736-747 [Zbl 1333.68131]
Moldenhauer, Carsten, Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs, 748-759 [Zbl 1334.68303]
Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory, Steiner transitive-closure spanners of low-dimensional posets, 760-772 [Zbl 1333.68203]
Ding, Hu; Xu, Jinhui, Solving the chromatic cone clustering problem via minimum spanning sphere, 773-784 [Zbl 1333.68292]
Lokshtanov, Daniel; Marx, Dániel, Clustering with local restrictions, 785-797 [Zbl 1333.68148]

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
Full Text: DOI