×

zbMATH — the first resource for mathematics

Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. (English) Zbl 1142.68001
Lecture Notes in Computer Science 5125. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). xxiii, 896 p. (2008).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding colloquium has been reviewed (see Zbl 1119.68002). For the second part of the proceedings of the present colloquium see Zbl 1141.68001.
Indexed articles:
Courcelle, Bruno, Graph structure and monadic second-order logic: Language theoretical aspects, 1-13 [Zbl 1143.68433]
Buchfuhrer, David; Umans, Christopher, The complexity of Boolean formula minimization, 24-35 [Zbl 1152.68445]
Dachman-Soled, Dana; Lee, Homin K.; Malkin, Tal; Servedio, Rocco A.; Wan, Andrew; Wee, Hoeteck, Optimal cryptographic hardness of learning monotone functions, 36-47 [Zbl 1152.94412]
Boros, Endre; Elbassioni, Khaled; Makino, Kazuhisa, On Berge multiplication for monotone Boolean dualization, 48-59 [Zbl 1152.94459]
Saxena, Nitin, Diagonal circuit identity testing and lower bounds, 60-71 [Zbl 1152.68703]
Yin, Yitong, Cell-probe proofs and nondeterministic cell-probe complexity, 72-83 [Zbl 1152.68432]
Ružić, Milan, Constructing efficient dictionaries in close to sorting time, 84-95 [Zbl 1152.68429]
Albers, Susanne; Lauer, Sonja, On list update with locality of reference, 96-107 [Zbl 1152.68425]
Blelloch, Guy E.; Vassilevska, Virginia; Williams, Ryan, A new combinatorial approach for sparse graph problems, 108-120 [Zbl 1152.68426]
Avin, Chen; Koucký, Michal; Lotker, Zvi, How to explore a fast-changing world (cover time of a simple random walk on evolving graphs), 121-132 [Zbl 1152.68476]
Chaintreau, Augustin; Fraigniaud, Pierre; Lebhar, Emmanuelle, Networks become navigable as nodes move and forget, 133-144 [Zbl 1152.68326]
Pritchard, David, Fast distributed computation of cuts via random circulations, 145-160 [Zbl 1152.68486]
Chebolu, Prasad; Frieze, Alan; Melsted, Páll, Finding a maximum matching in a sparse random graph in \(O(n)\) expected time, 161-172 [Zbl 1152.05372]
Cicalese, Ferdinando; Laber, Eduardo Sany, Function evaluation via linear programming in the priced information model, 173-185 [Zbl 1152.68446]
Azar, Yossi; Birnbaum, Benjamin; Karlin, Anna R.; Mathieu, Claire; Nguyen, C. Thach, Improved approximation algorithms for budgeted allocations, 186-197 [Zbl 1152.68700]
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko, The travelling salesman problem in bounded degree graphs, 198-209 [Zbl 1152.90575]
Fomin, Fedor V.; Villanger, Yngve, Treewidth computation and extremal combinatorics, 210-221 [Zbl 1152.05376]
Plaxton, C. Greg, Fast scheduling of weighted unit jobs with release times and deadlines, 222-233 [Zbl 1152.90459]
Jansen, Klaus; Thöle, Ralf, Approximation algorithms for scheduling parallel jobs: Breaking the approximation ratio of 2, 234-245 [Zbl 1152.90446]
Eisenbrand, Friedrich; Rothvoß, Thomas, A PTAS for static priority real-time scheduling with resource augmentation, 246-257 [Zbl 1152.90438]
Alon, Noga; Hod, Rani, Optimal monotone encodings, 258-270 [Zbl 1153.68376]
Iwama, Kazuo; Nishimura, Harumichi; Paterson, Mike; Raymond, Rudy; Yamashita, Shigeru, Polynomial-time construction of linear network coding, 271-282 [Zbl 1153.68320]
Cheng, Qi; Wan, Daqing, Complexity of decoding positive-rate Reed-Solomon codes, 283-293 [Zbl 1153.94468]
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan, Computational complexity of the distance constrained labeling problem for trees (extended abstract), 294-305 [Zbl 1153.68390]
Pemmaraju, Sriram; Srinivasan, Aravind, The randomized coloring procedure with symmetry-breaking, 306-319 [Zbl 1153.05332]
Chierichetti, Flavio; Vattani, Andrea, The local nature of list colorings for graphs of high girth, 320-332 [Zbl 1153.05316]
Kawarabayashi, Ken-ichi, Approximating list-coloring on a fixed surface, 333-344 [Zbl 1153.05319]
Bläser, Markus; Hardt, Moritz; Steurer, David, Asymptotically optimal hitting sets against polynomials, 345-356 [Zbl 1153.68569]
Andoni, Alexandr; Krauthgamer, Robert, The smoothed complexity of edit distance, 357-369 [Zbl 1153.68563]
Kao, Ming-Yang; Schweller, Robert, Randomized self-assembly for approximate shapes, 370-384 [Zbl 1153.68561]
Dietzfelbinger, Martin; Pagh, Rasmus, Succinct data structures for retrieval and approximate membership (extended abstract), 385-396 [Zbl 1153.68364]
Dimitrov, Nedialko B.; Plaxton, C. Greg, Competitive weighted matching in transversal matroids, 397-408 [Zbl 1153.05328]
Bansal, Nikhil; Chan, Ho-Leung; Lam, Tak-Wah; Lee, Lap-Kei, Scheduling for speed bounded processors, 409-420 [Zbl 1153.68334]
Haeupler, Bernhard; Kavitha, Telikepalli; Mathew, Rogers; Sen, Siddhartha; Tarjan, Robert E., Faster algorithms for incremental topological ordering, 421-433 [Zbl 1153.05329]
Frandsen, Gudmund Skovbjerg; Sankowski, Piotr, Dynamic normal forms and dynamic characteristic polynomial, 434-446 [Zbl 1153.65332]
Phillips, Jeff M., Algorithms for \(\varepsilon \)-approximations of terrains, 447-458 [Zbl 1153.68568]
Laber, Eduardo; Molinaro, Marco, An approximation algorithm for binary searching in trees, 459-471 [Zbl 1153.68567]
Chekuri, Chandra; Khanna, Sanjeev, Algorithms for 2-route cut problems, 472-484 [Zbl 1153.68566]
Borradaile, Glencora; Klein, Philip, The two-edge connectivity survivable network problem in planar graphs, 485-501 [Zbl 1153.68565]
Diakonikolas, Ilias; Lee, Homin K.; Matulef, Kevin; Servedio, Rocco A.; Wan, Andrew, Efficiently testing sparse GF(2) polynomials, 502-514 [Zbl 1153.68570]
Onak, Krzysztof, Testing properties of sets of points in metric spaces, 515-526 [Zbl 1153.68473]
Kale, Satyen; Seshadhri, C., An expansion tester for bounded degree graphs, 527-538 [Zbl 1153.68466]
Yoshida, Yuichi; Ito, Hiro, Property testing on \(k\)-vertex-connectivity of graphs, 539-550 [Zbl 1153.68497]
Razgon, Igor; O’Sullivan, Barry, Almost 2-SAT is fixed-parameter tractable (extended abstract), 551-562 [Zbl 1153.68397]
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny, On problems without polynomial kernels (extended abstract), 563-574 [Zbl 1153.68554]
Koutis, Ioannis, Faster algebraic algorithms for path and packing problems, 575-586 [Zbl 1153.68562]
Chen, Yijia; Thurley, Marc; Weyer, Mark, Understanding the complexity of induced subgraph isomorphisms, 587-596 [Zbl 1153.68387]
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A., Spanners in sparse graphs, 597-608 [Zbl 1153.68406]
Baswana, Surender; Gaur, Akshay; Sen, Sandeep; Upadhyay, Jayant, Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error, 609-621 [Zbl 1153.68405]
Roditty, Liam; Shapira, Asaf, All-pairs shortest paths with a sublinear additive error, 622-633 [Zbl 1153.68409]
Tedder, Marc; Corneil, Derek; Habib, Michel; Paul, Christophe, Simpler linear-time modular decomposition via recursive factorizing permutations, 634-645 [Zbl 1153.68410]
Bulatov, Andrei A., The complexity of the counting constraint satisfaction problem, 646-661 [Zbl 1153.68386]
Krokhin, Andrei; Marx, Dániel, On the hardness of losing weight, 662-673 [Zbl 1153.68382]
Lee, Troy; Mittal, Rajat, Product theorems via semidefinite programming, 674-685 [Zbl 1153.68396]
Ben-Sasson, Eli; Harsha, Prahladh; Lachish, Oded; Matsliah, Arie, Sound 3-query PCPPs are long, 686-697 [Zbl 1153.68440]
Esparza, Javier; Gawlitza, Thomas; Kiefer, Stefan; Seidl, Helmut, Approximative methods for monotone systems of min-max-polynomial equations, 698-710 [Zbl 1153.65337]
Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis, Recursive stochastic games with positive rewards, 711-723 [Zbl 1153.91328]
Kähler, Detlef; Wilke, Thomas, Complementation, disambiguation, and determinization of Büchi automata unified, 724-735 [Zbl 1153.68032]
Greco, Gianluigi; Scarcello, Francesco, Tree projections: Hypergraph games and minimality, 736-747 [Zbl 1153.91369]
Porat, Ely; Rothschild, Amir, Explicit non-adaptive combinatorial group testing schemes, 748-759 [Zbl 1153.68558]
Guha, Sudipto; McGregor, Andrew, Tight lower bounds for multi-pass stream computation via pass elimination, 760-772 [Zbl 1153.68381]
Regev, Oded; Schiff, Liron, Impossibility of a quantum speed-up with a faulty oracle, 773-781 [Zbl 1153.68365]
Hallgren, Sean; Harrow, Aram W., Superpolynomial speedups based on almost any quantum circuit, 782-795 [Zbl 1153.68378]
Fanelli, Angelo; Flammini, Michele; Moscardelli, Luca, The speed of convergence in congestion games under best-response dynamics, 796-807 [Zbl 1153.91308]
Briest, Patrick, Uniform budgets and the envy-free pricing problem, 808-819 [Zbl 1153.91417]
Christodoulou, George; Kovács, Annamária; Schapira, Michael, Bayesian combinatorial auctions, 820-832 [Zbl 1153.91436]
Azar, Yossi; Gamzu, Iftah, Truthful unification framework for packing integer programs with choices, 833-844 [Zbl 1153.90525]
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald, Upper bounds on the noise threshold for fault-tolerant quantum computing, 845-856 [Zbl 1153.81467]
Mhalla, Mehdi; Perdrix, Simon, Finding optimal flows efficiently, 857-868 [Zbl 1153.68379]
Childs, Andrew M.; Lee, Troy, Optimal quantum adversary lower bounds for ordered search, 869-880 [Zbl 1153.68363]
Eldar, Lior; Regev, Oded, Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete, 881-892 [Zbl 1153.81465]

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