Skip to main content

Papers accepted to track A of ICALP 2012

  1. Jens M. Schmidt. Certifying 3-Connectivitiy in Linear Time
  2. Stacey Jeffery, Robin Kothari and Frédéric Magniez. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
  3. Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)
  4. Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter. Regular Languages are Church-Rosser Congruential
  5. John Fearnley and Sven Schewe. Time and Parallelizability Results for Parity Games with Bounded Treewidth
  6. Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. CRAM: Compressed Random Access Memory
  7. Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Applications
  8. Elad Verbin and Qin Zhang. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
  9. Sungjin Im, Viswanath Nagarajan and Ruben Van Der Zwaan. Minimum Latency Submodular Cover
  10. Hongfei Fu. Computing Game Metrics on Markov Decision Processes
  11. Yaron Velner. The Complexity of Mean-Payoff Automaton Expression
  12. Denis Kuperberg and Michael Vanden Boom. On the Expressive Power of Cost Logics over Infinite Words.
  13. Shelby Kimmel. Quantum Adversary (Upper) Bound
  14. Ran Gelles, Rafail Ostrovsky and Kina Winoto. Multi-User Equality Testing and Its Applications
  15. Marcel Ochel, Klaus Radke and Berthold Voecking. Online Packing with Gradually Improving Capacity Estimations with Applications to Network Lifetime Maximization
  16. László Babai, Paolo Codenotti and Youming Qiao. Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups
  17. Pushkar Tripathi, Prasad Tetali and Kevin Costello. Stochastic Matching with Commitment
  18. Michael Goodrich and Michael Mitzenmacher. Anonymous Card Shuffling and its Applications to Parallel Mixnets
  19. Magnus M. Halldorsson, Xiaoming Sun, Mario Szegedy and Chengu Wang. Streaming and Communication Complexity of Clique Approximation
  20. Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlstrom. Clique cover and graph separation: New incompressibility results
  21. Tomáš Gavenčiak, Daniel Kral and Sang-Il Oum. Deciding first order logic properties of matroids
  22. Robert Krauthgamer and Tamar Zondiner. Preserving Terminal Distances using Minors
  23. Marco Molinaro and R Ravi. Geometry of Online Packing Linear Programs
  24. Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth
  25. Yoann Dieudonne and Andrzej Pelc. Deterministic network exploration by anonymous silent agents with local traffic reports
  26. Bingkai Lin and Yijia Chen. The parameterized complexity of k-edge induced subgraphs
  27. Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk. Minimizing Rosenthal Potential in Multicast Games
  28. Yuval Emek, Magnus M. Halldorsson and Adi Rosen. Space-Constrained Interval Selection
  29. T-H. Hubert Chan, Mingfei Li and Li Ning. Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
  30. Lukas Polacek and Ola Svensson. Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
  31. Justin Hsu, Sanjeev Khanna and Aaron Roth. Distributed Private Heavy Hitters
  32. Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos and Yaron Singer. Efficiency-Revenue Trade-offs in Auctions
  33. Inge Li Gørtz, Viswanath Nagarajan and Rishi Saket. Stochastic Vehicle Routing with Recourse
  34. Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald and He Sun. Counting Arbitrary Subgraphs in Data Streams
  35. Nicole Megow, Martin Skutella, Jose Verschae and Andreas Wiese. The Power of Recourse for Online MST and TSP
  36. Piotr Krysta and Berthold Voecking. Online Mechanism Design (Randomized Rounding on the Fly)
  37. Anupam Gupta and Viswanath Nagarajan. Approximating Sparse Covering Integer Programs Online
  38. Bundit Laekhanukit, Shayan Oveis Gharan and Mohit Singh. An Improved Approximation Algorithm for The Minimum Size k-Arc Connected Subgraph Problem
  39. Andrew Hughes, A Pavan, Nathan Russell and Alan Selman. A Thirty Year Old Conjecture about Promise Problems
  40. Maria Florina Balcan and Yingyu Liang. Clustering under Perturbation Resilience
  41. Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
  42. Hiro Ito, Shin-Ichi Tanigawa and Yuichi Yoshida. Constant-Time Algorithms for Sparsity Matroids
  43. Bruno Bauwens. Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity
  44. Joshua Baron, Rafail Ostrovsky and Ivan Visconti. Nearly Simultaneously Resettable Black-Box Zero Knowledge
  45. Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems
  46. Michael Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai. Parameterized Approximation via Fidelity Preserving Transformations
  47. Niv Buchbinder, Seffi Naor, R. Ravi and Mohit Singh. Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
  48. Yossi Azar and Iftah Gamzu. Efficient Submodular Function Maximization under Linear Packing Constraints
  49. Ning Chen, Xiaotie Deng, Hongyang Zhang and Jie Zhang. Incentive Ratios of Fisher Markets
  50. Uriel Feige and Shlomo Jozeph. Universal Factor Graphs
  51. Leonid Barenboim. On the Locality of NP-Complete Problems
  52. Khaled Elbassioni. A QPTAS for $\eps$-Envy-Free Profit-Maximizing Pricing on Line Graphs
  53. C.-H. Luke Ong and Takeshi Tsukada. Two-Level Game Semantics, Intersection Types and Recursion Schemes
  54. Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs and Madars Virza. Quantum strategies are better than classical in almost any XOR game
  55. Reut Levi, Dana Ron and Ronitt Rubinfeld. Testing Similar Means
  56. Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie. Converting Online Algorithms To Local Computation Algorithms
  57. Reuven Bar-Yehuda, Erez Kantor, Shay Kutten and Dror Rawitz. Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs
  58. Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii and Michael Zakharyaschev. Exponential Lower Bounds and Separation for Query Rewriting
  59. Deeparnab Chakrabarty and Zhiyi Huang. Testing Coverage Functions
  60. S. Laplante, V. Lerays and J. Roland. Classical and quantum partition bound and detector inefficiency
  61. Michael Dinitz, Guy Kortsarz and Ran Raz. Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
  62. Sylvain Salvati, Giulio Manzonetto, Mai Gehrke and Henk Barendregt. Urzyczyn and Loader are Logically Related
  63. Michael Benedikt, Pierre Bourhis and Pierre Senellart. Monadic Datalog Containment
  64. Danny Z. Chen and Haitao Wang. Computing the Visibility Polygon of an Island in a Polygonal Domain
  65. Amit Deshpande, Ravindran Kannan and Nikhil Srivastava. Zero-One Rounding of Singular Vectors
  66. Mikolaj Bojańczyck and Thomas Place. Regular Languages of Infinite Trees that are Boolean Combinations of Open Sets
  67. Mikolaj Bojanczyk and Thomas Place. Model theory in nominal sets
  68. Patricia Bouyer, Nicolas Markey and Ocan Sankur. Robust Reachability in Timed Automata: A Game-based Approach
  69. Nishanth Chandran, Juan Garay and Rafail Ostrovsky. Edge Fault Tolerance on Sparse Networks
  70. Serge Gaspers and Stefan Szeider. Backdoors to Acyclic SAT
  71. Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese. Assigning Sporadic Tasks to Unrelated Parallel Machines
  72. Rajeev Alur and Loris D'Antoni. Streaming Tree Transducers
  73. Elias Koutsoupias and Katia Papakonstantinopoulou. Contention issues in congestion games
  74. Luca Aceto, Arnaud Carayol, Zoltan Esik and Anna Ingolfsdottir. Algebraic Synchronization Trees and Processes
  75. Artur Jeż. Faster fully compressed pattern matching by recompression
  76. Ramanujan M. S. and Daniel Lokshtanov. Parameterized Tractability of Multiway Cut with Parity Constraints
  77. Karl Bringmann and Konstantinos Panagiotou. Efficient Sampling Methods for Discrete Distributions
  78. Robert Crowston, Mark Jones and Matthias Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound
  79. Chris Broadbent, Arnaud Carayol, Matthew Hague and Olivier Serre. A Saturation Method for Collapsible Pushdown Systems
  80. Tomas Brazdil, Antonin Kucera, Petr Novotný and Dominik Wojtczak. Minimizing Expected Termination Time in One-Counter Markov Decision Processes
  81. Gilles Dowek and Pablo Arrighi. Causal graph dynamics
  82. Manfred Kufleitner and Alexander Lauser. Lattices of Logical Fragments over Words
  83. Bjarki Holm and Anuj Dawar. Pebble Games with Algebraic Rules
  84. Mikołaj Bojańczyk and Sławomir Lasota. Application of nominal sets to machine-independent characterization of timed languages
  85. Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs
  86. Moses Charikar and Shi Li. A Dependent LP-rounding Approach for the $k$-Median Problem
  87. Loukas Georgiadis and Robert Tarjan. Dominators, Directed Bipolar Orders, and Independent Spanning Trees
  88. Chandra Chekuri, Alina Ene and Ali Vakilian. Node-weighted Network Design in Planar and Minor-closed Families of Graphs
  89. Anindya De, Ilias Diakonikolas and Rocco Servedio. The Inverse Shapley Value Problem
  90. Andrzej Murawski and Nikos Tzevelekos. Algorithmic games for full ground references
  91. Arash Farzan, Ian Munro and Rajeev Raman. Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
  92. Michael Rabin, Yishay Mansour, Muthu Muthuikrishnan and Moti Yung. Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
  93. Marcelo Fiore. Generalised Polynomial Functors: Theory and Applications
  94. Siddharth Barman, Shuchi Chawla, David Malec and Seeun Umboh. Secretary Problems with Convex Costs
  95. Michael Kapralov and Rina Panigrahy. NNS lower bounds via metric expansion for $l_\infty$ and $EMD$
  96. Rahul Santhanam and Srikanth Srinivasan. On the Limits of Sparsification
  97. Szymon Toruńczyk. Languages of profinite words and the limitedness problem
  98. Matthew Patitz, Robert Schweller, Bin Fu and Robert Sheline. Self-Assembly with Geometric Tiles
  99. David Peleg, Liam Roditty and Elad Tal. Distributed Algorithms for Network Diameter and Girth
  100. Navendu Jain, Ishai Menache, Joseph Naor and F. Bruce Shepherd. Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks
  101. Barna Saha and Samir Khuller. Set Cover Revisited: Hypergraph Cover with Hard Capacities
  102. Yaoyun Shi and Xiaodi Wu. Epsilon-net method for optimizations over separable states
  103. Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan. Quadratic Programming with a Ratio Objective
  104. Tadeusz Litak, Dirk Pattinson, Katsuhiko Sano and Lutz Schröder. Coalgebraic Predicate Logic
  105. Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
  106. Grigore Rosu and Andrei Stefanescu. Towards a Unified Theory of Operational and Axiomatic Semantics
  107. Maribel Fernandez and Albert Rubio. Nominal Completion for Rewrite Systems with Binders
  108. Andrew Berns, Sriram Pemmaraju and James Hegeman. Super-Fast Distributed Algorithms for Metric Facility Location
  109. Jaroslaw Byrka and Bartosz Rybicki. Improved LP-rounding approximation algorithm for $k$-level uncapacitated facility location
  110. Luca Gugelmann, Konstantinos Panagiotou and Ueli Peter. Hyperbolic Random Graphs: Degree Sequence and Clustering
  111. Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach and Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP
  112. Philip Klein and Dániel Marx. Solving planar $k$-terminal cut in $O(n^{c \sqrt{k}})$ time
  113. Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam and Vassilis Zikas. Byzantine Agreement with a Rational Adversary
  114. Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden and Aneesh Sharma. Preventing Unraveling in Social Networks: The Anchored k-Core Problem
  115. Anupam Gupta and Kevin Lewi. The Online Metric Matching Problem for Doubling Metrics
  116. Dimitris Achlioptas and Ricardo Menchaca-Mendez. Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method
  117. Prosenjit Bose, Sebastien Collette, Rolf Fagerberg and Stefan Langerman. De-amortizing Binary Search Trees
  118. Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen. The NOF Multiparty Communication Complexity of Composed Functions
  119. Christopher Broadbent. Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
  120. Justin Thaler, Jonathan Ullman and Salil Vadhan. Faster Algorithms for Privately Releasing Marginals
  121. Anuj Dawar and Albert Atserias. Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers
  122. Uday Reddy and Brian Dunphy. An automata-theoretic model of Idealized Algol An automata-theoretic model of Idealized Algol