Automata, Languages, and Programming 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings. Part I /
This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and se...
| Corporate Authors: | International Colloquium on Automata, Languages, and Programming Warwick, England) |
|---|---|
| Other Authors: | International Colloquium on Automata, Languages, and Programming, Czumaj, Artur., SpringerLink (Online service) |
| Format: | eBook |
| Language: | English |
| Published: |
Berlin ; New York :
Springer,
©2012.
Berlin ; New York : [2012] |
| Physical Description: |
1 online resource. |
| Series: |
Lecture notes in computer science ;
7391. Lecture notes in computer science. Advanced research in computing and software science. LNCS sublibrary. Theoretical computer science and general issues. |
| Subjects: |
| LEADER | 13055cam a2201081 a 4500 | ||
|---|---|---|---|
| 001 | 797966055 | ||
| 003 | OCoLC | ||
| 005 | 20240223121953.0 | ||
| 006 | m o d | ||
| 007 | cr cnu---unuuu | ||
| 008 | 120702s2012 gw ob 101 0 eng d | ||
| 019 | |a 1058652325 | ||
| 020 | |a 9783642315947 |q (electronic bk.) | ||
| 020 | |a 3642315941 |q (electronic bk.) | ||
| 020 | |z 9783642315930 | ||
| 024 | 7 | |a 10.1007/978-3-642-31594-7 |2 doi | |
| 035 | |a (OCoLC)797966055 |z (OCoLC)1058652325 | ||
| 040 | |a GW5XE |b eng |e pn |c GW5XE |d ZMC |d COO |d ZMC |d OCLCQ |d E7B |d OCLCF |d BEDGE |d VT2 |d OCLCO |d YDXCP |d OCL |d OCLCO |d EBLCP |d ESU |d IOG |d NJR |d REB |d CEF |d U3W |d WYU |d AU@ |d YOU |d TKN |d OCLCQ |d LEAUB |d OCLCQ |d AJS |d OCLCQ |d OCLCO |d OCLCQ |d OCLCO |d OCLCQ |d OCLCO |d OCLCL | ||
| 049 | |a COM6 | ||
| 050 | 4 | |a QA76.7 |b .I58 2012 | |
| 082 | 0 | 4 | |a 005.1/3 |2 23 |
| 111 | 2 | |a International Colloquium on Automata, Languages, and Programming |n (39th : |d 2012 : |c Warwick, England) | |
| 245 | 1 | 0 | |a Automata, Languages, and Programming : |b 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings. |n Part I / |c Artur Czumaj [and others] (eds.). |
| 246 | 3 | |a ICALP 2012. | |
| 260 | |a Berlin ; |a New York : |b Springer, |c ©2012. | ||
| 264 | 1 | |a Berlin ; |a New York : |b Springer, |c [2012] | |
| 264 | 4 | |c ©2012. | |
| 300 | |a 1 online resource. | ||
| 336 | |a text |b txt |2 rdacontent. | ||
| 337 | |a computer |b c |2 rdamedia. | ||
| 338 | |a online resource |b cr |2 rdacarrier. | ||
| 490 | 1 | |a Lecture notes in computer science, |x 0302-9743 ; |v 7391. | |
| 490 | 1 | |a Advanced research in computing and software science. | |
| 490 | 1 | |a LNCS sublibrary. SL 1, Theoretical computer science and general issues. | |
| 500 | |a International conference proceedings. | ||
| 505 | 0 | 0 | |t Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method / |r Dimitris Achlioptas and Ricardo Menchaca-Mendez -- |t The NOF Multiparty Communication Complexity of Composed Functions / |r Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen -- |t Quantum Strategies Are Better Than Classical in Almost Any XOR Game / |r Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis, Dmitrijs Kravčenko and Raitis Ozols, et al. -- |t Efficient Submodular Function Maximization under Linear Packing Constraints / |r Yossi Azar and Iftah Gamzu -- |t Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups |g (Extended Abstract) / |r László Babai, Paolo Codenotti and Youming Qiao -- |t Clustering under Perturbation Resilience / |r Maria Florina Balcan and Yingyu Liang -- |t Secretary Problems with Convex Costs / |r Siddharth Barman, Seeun Umboh, Shuchi Chawla and David Malec -- |t Nearly Simultaneously Resettable Black-Box Zero Knowledge / |r Joshua Baron, Rafail Ostrovsky and Ivan Visconti -- |t Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity / |r Bruno Bauwens -- |t On Quadratic Programming with a Ratio Objective / |r Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan -- |t De-amortizing Binary Search Trees / |r Prosenjit Bose, Sébastien Collette, Rolf Fagerberg and Stefan Langerman -- |t Efficient Sampling Methods for Discrete Distributions / |r Karl Bringmann and Konstantinos Panagiotou -- |t Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints / |r Niv Buchbinder, Joseph (Seffi) Naor, R. Ravi and Mohit Singh -- |t Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location / |r Jaroslaw Byrka and Bartosz Rybicki -- |t Testing Coverage Functions / |r Deeparnab Chakrabarty and Zhiyi Huang -- |t Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree / |r T. -H. Hubert Chan, Mingfei Li and Li Ning. |
| 505 | 8 | 0 | |t A Dependent LP-Rounding Approach for the k-Median Problem / |r Moses Charikar and Shi Li -- |t Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs / |r Chandra Chekuri, Alina Ene and Ali Vakilian -- |t Computing the Visibility Polygon of an Island in a Polygonal Domain / |r Danny Z. Chen and Haitao Wang -- |t Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable / |r Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx -- |t Max-Cut Parameterized above the Edwards-Erdős Bound / |r Robert Crowston, Mark Jones and Matthias Mnich -- |t Clique Cover and Graph Separation: New Incompressibility Results / |r Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström -- |t The Inverse Shapley Value Problem / |r Anindya De, Ilias Diakonikolas and Rocco Servedio -- |t Zero-One Rounding of Singular Vectors / |r Amit Deshpande, Ravindran Kannan and Nikhil Srivastava -- |t Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner / |r Michael Dinitz, Guy Kortsarz and Ran Raz -- |t Space-Constrained Interval Selection / |r Yuval Emek, Magnús M. Halldórsson and Adi Rosén -- |t Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations / |r Kousha Etessami, Alistair Stewart and Mihalis Yannakakis -- |t Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima / |r Arash Farzan, J. Ian Munro and Rajeev Raman -- |t Universal Factor Graphs / |r Uriel Feige and Shlomo Jozeph -- |t Parameterized Approximation via Fidelity Preserving Transformations / |r Michael R. Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai -- |t Backdoors to Acyclic SAT / |r Serge Gaspers and Stefan Szeider -- |t Dominators, Directed Bipolar Orders, and Independent Spanning Trees / |r Loukas Georgiadis and Robert E. Tarjan -- |t Hardness of Approximation for Quantum Problems / |r Sevag Gharibian and Julia Kempe. |
| 505 | 8 | 0 | |t The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) / |r Leslie Ann Goldberg and Mark Jerrum -- |t Stochastic Vehicle Routing with Recourse / |r Inge Li Gørtz, Viswanath Nagarajan and Rishi Saket -- |t The Online Metric Matching Problem for Doubling Metrics / |r Anupam Gupta and Kevin Lewi -- |t Approximating Sparse Covering Integer Programs Online / |r Anupam Gupta and Viswanath Nagarajan -- |t Streaming and Communication Complexity of Clique Approximation / |r Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy and Chengu Wang -- |t Distributed Private Heavy Hitters / |r Justin Hsu, Sanjeev Khanna and Aaron Roth -- |t A Thirty Year Old Conjecture about Promise Problems / |r Andrew Hughes, A. Pavan, Nathan Russell and Alan Selman -- |t Minimum Latency Submodular Cover / |r Sungjin Im, Viswanath Nagarajan and Ruben van der Zwaan -- |t Constant-Time Algorithms for Sparsity Matroids / |r Hiro Ito, Shin-Ichi Tanigawa and Yuichi Yoshida -- |t CRAM: Compressed Random Access Memory / |r Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung -- |t Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision / |r Stacey Jeffery, Robin Kothari and Frédéric Magniez -- |t Faster Fully Compressed Pattern Matching by Recompression / |r Artur Jeż -- |t NNS Lower Bounds via Metric Expansion for l{u221E} and EMD / |r Michael Kapralov and Rina Panigrahy -- |t Quantum Adversary (Upper) Bound / |r Shelby Kimmel -- |t Solving Planar k-Terminal Cut in O(nc Ök)O(nck) Time / |r Philip N. Klein and Dániel Marx -- |t Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs / |r Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström -- |t Preserving Terminal Distances Using Minors / |r Robert Krauthgamer and Tamar Zondiner -- |t A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem / |r Bundit Laekhanukit, Shayan Oveis Gharan and Mohit Singh -- |
| 505 | 8 | 0 | |t Classical and Quantum Partition Bound and Detector Inefficiency / |r Sophie Laplante, Virginie Lerays and Jérémie Roland -- |t Testing Similar Means / |r Reut Levi, Dana Ron and Ronitt Rubinfeld -- |t The Parameterized Complexity of k-Edge Induced Subgraphs / |r Bingkai Lin and Yijia Chen -- |t Converting Online Algorithms to Local Computation Algorithms / |r Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie -- |t Assigning Sporadic Tasks to Unrelated Parallel Machines / |r Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese -- |t A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals / |r Dániel Marx -- |t The Power of Recourse for Online MST and TSP / |r Nicole Megow, Martin Skutella, José Verschae and Andreas Wiese -- |t Geometry of Online Packing Linear Programs / |r Marco Molinaro and R. Ravi -- |t Self-assembly with Geometric Tiles / |r Bin Fu, Matthew J. Patitz, Robert T. Schweller and Robert Sheline -- |t Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation / |r Lukas Polacek and Ola Svensson -- |t Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions / |r Michael O. Rabin, Yishay Mansour, S. Muthukrishnan and Moti Yung -- |t Parameterized Tractability of Multiway Cut with Parity Constraints / |r Daniel Lokshtanov and M.S. Ramanujan -- |t Set Cover Revisited: Hypergraph Cover with Hard Capacities / |r Barna Saha and Samir Khuller -- |t On the Limits of Sparsification / |r Rahul Santhanam and Srikanth Srinivasan -- |t Certifying 3-Connectivity in Linear Time / |r Jens M. Schmidt -- |t Epsilon-Net Method for Optimizations over Separable States / |r Yaoyun Shi and Xiaodi Wu -- |t Faster Algorithms for Privately Releasing Marginals / |r Justin Thaler, Jonathan Ullman and Salil Vadhan -- |t Stochastic Matching with Commitment / |r Kevin P. Costello, Prasad Tetali and Pushkar Tripathi -- |t Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance / |r Elad Verbin and Qin Zhang -- |t A Matrix Hyperbolic Cosine Algorithm and Applications / |r Anastasios Zouzias. |
| 504 | |a Includes bibliographical references and author index. | ||
| 520 | |a This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation. | ||
| 650 | 0 | |a Programming languages (Electronic computers) |v Congresses. | |
| 650 | 0 | |a Computer programming |v Congresses. | |
| 650 | 6 | |a Programmation (Informatique) |v Congrès. | |
| 650 | 7 | |a Informatique. |2 eclas. | |
| 650 | 7 | |a Computer programming. |2 fast. | |
| 650 | 7 | |a Programming languages (Electronic computers) |2 fast. | |
| 653 | 4 | |a Computer science. | |
| 653 | 4 | |a Computer Communication Networks. | |
| 653 | 4 | |a Computer software. | |
| 653 | 4 | |a Computational complexity. | |
| 653 | 4 | |a Information storage and retrieval systems. | |
| 653 | 4 | |a Algorithm Analysis and Problem Complexity. | |
| 653 | 4 | |a Computation by Abstract Devices. | |
| 653 | 4 | |a Information Storage and Retrieval. | |
| 653 | 4 | |a Discrete Mathematics in Computer Science. | |
| 655 | 7 | |a Conference papers and proceedings. |2 fast. | |
| 655 | 7 | |a Software. |2 lcgft. | |
| 655 | 7 | |a Conference papers and proceedings. |2 lcgft. | |
| 700 | 1 | |a Czumaj, Artur. | |
| 710 | 2 | |a SpringerLink (Online service) | |
| 776 | 0 | 8 | |i Printed edition: |z 9783642315930. |
| 830 | 0 | |a Lecture notes in computer science ; |v 7391. | |
| 830 | 0 | |a Lecture notes in computer science. |p Advanced research in computing and software science. | |
| 830 | 0 | |a LNCS sublibrary. |n SL 1, |p Theoretical computer science and general issues. | |
| 907 | |a .b3622179x |b multi |c - |d 120912 |e 240320 | ||
| 998 | |a (3)cue |a cu |b 240227 |c m |d z |e - |f eng |g gw |h 0 |i 2 | ||
| 948 | |a MARCIVE Overnight, in 2024.03 | ||
| 948 | |a MARCIVE Comprehensive, in 2023.06 | ||
| 948 | |a MARCIVE Comp, in 2022.12 | ||
| 948 | |a MARCIVE Over, 07/2021 | ||
| 948 | |a MARCIVE Comp, 2019.12 | ||
| 948 | |a MARCIVE Comp, 2018.05 | ||
| 948 | |a MARCIVE Comp, 2017.10 | ||
| 948 | |a MARCIVE August, 2017 | ||
| 948 | |a MARCIVE extract Aug, 5 2017 | ||
| 994 | |a 92 |b COM | ||
| 995 | |a Loaded with m2btab.ltiac in 2024.03 | ||
| 995 | |a Loaded with m2btab.elec in 2024.02 | ||
| 995 | |a Loaded with m2btab.ltiac in 2023.06 | ||
| 995 | |a Loaded with m2btab.ltiac in 2022.12 | ||
| 995 | |a Loaded with m2btab.ltiac in 2021.07 | ||
| 995 | |a Loaded with m2btab.elec in 2021.06 | ||
| 995 | |a Loaded with m2btab.ltiac in 2019.12 | ||
| 995 | |a Loaded with m2btab.ltiac in 2018.06 | ||
| 995 | |a Loaded with m2btab.ltiac in 2017.10 | ||
| 995 | |a Loaded with m2btab.ltiac in 2017.08 | ||
| 995 | |a Loaded with m2btab.elec in 2016 | ||
| 995 | |a Loaded with m2btab.elec in 2016 | ||
| 995 | |a OCLC offline update by CMU | ||
| 999 | |e z | ||
| 999 | |a cue | ||
| 989 | |d cueme |e - - |f - - |g - |h 0 |i 0 |j 200 |k 240227 |l $0.00 |m |n - - |o - |p 0 |q 0 |t 0 |x 0 |w SpringerLink |1 .i150317268 |u http://ezproxy.coloradomesa.edu/login?url=https://link.springer.com/10.1007/978-3-642-31594-7 |3 SpringerLink |z Click here for access | ||