Skip to main content

Papers accepted to track A of ICALP 2012

  • Jens M. Schmidt. Certifying 3-Connectivitiy in Linear Time
  • Stacey Jeffery, Robin Kothari and Frédéric Magniez. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
  • Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)
  • Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. CRAM: Compressed Random Access Memory
  • Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Applications
  • Elad Verbin and Qin Zhang. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
  • Sungjin Im, Viswanath Nagarajan and Ruben Van Der Zwaan. Minimum Latency Submodular Cover
  • Shelby Kimmel. Quantum Adversary (Upper) Bound
  • László Babai, Paolo Codenotti and Youming Qiao. Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups
  • Pushkar Tripathi, Prasad Tetali and Kevin Costello. Stochastic Matching with Commitment
  • Magnus M. Halldorsson, Xiaoming Sun, Mario Szegedy and Chengu Wang. Streaming and Communication Complexity of Clique Approximation
  • Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlstrom. Clique cover and graph separation: New incompressibility results
  • Robert Krauthgamer and Tamar Zondiner. Preserving Terminal Distances using Minors
  • Marco Molinaro and R Ravi. Geometry of Online Packing Linear Programs
  • Bingkai Lin and Yijia Chen. The parameterized complexity of k-edge induced subgraphs
  • Yuval Emek, Magnus M. Halldorsson and Adi Rosen. Space-Constrained Interval Selection
  • T-H. Hubert Chan, Mingfei Li and Li Ning. Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
  • Lukas Polacek and Ola Svensson. Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
  • Justin Hsu, Sanjeev Khanna and Aaron Roth. Distributed Private Heavy Hitters
  • Inge Li Gørtz, Viswanath Nagarajan and Rishi Saket. Stochastic Vehicle Routing with Recourse
  • Nicole Megow, Martin Skutella, Jose Verschae and Andreas Wiese. The Power of Recourse for Online MST and TSP
  • Anupam Gupta and Viswanath Nagarajan. Approximating Sparse Covering Integer Programs Online
  • Bundit Laekhanukit, Shayan Oveis Gharan and Mohit Singh. An Improved Approximation Algorithm for The Minimum Size k-Arc Connected Subgraph Problem
  • Andrew Hughes, A Pavan, Nathan Russell and Alan Selman. A Thirty Year Old Conjecture about Promise Problems
  • Maria Florina Balcan and Yingyu Liang. Clustering under Perturbation Resilience
  • Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
  • Hiro Ito, Shin-Ichi Tanigawa and Yuichi Yoshida. Constant-Time Algorithms for Sparsity Matroids
  • Bruno Bauwens. Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity
  • Joshua Baron, Rafail Ostrovsky and Ivan Visconti. Nearly Simultaneously Resettable Black-Box Zero Knowledge
  • Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems
  • Michael Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai. Parameterized Approximation via Fidelity Preserving Transformations
  • Niv Buchbinder, Seffi Naor, R. Ravi and Mohit Singh. Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
  • Yossi Azar and Iftah Gamzu. Efficient Submodular Function Maximization under Linear Packing Constraints
  • Uriel Feige and Shlomo Jozeph. Universal Factor Graphs
  • 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
  • Reut Levi, Dana Ron and Ronitt Rubinfeld. Testing Similar Means
  • Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie. Converting Online Algorithms To Local Computation Algorithms
  • Deeparnab Chakrabarty and Zhiyi Huang. Testing Coverage Functions
  • S. Laplante, V. Lerays and J. Roland. Classical and quantum partition bound and detector inefficiency
  • Michael Dinitz, Guy Kortsarz and Ran Raz. Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
  • Danny Z. Chen and Haitao Wang. Computing the Visibility Polygon of an Island in a Polygonal Domain
  • Amit Deshpande, Ravindran Kannan and Nikhil Srivastava. Zero-One Rounding of Singular Vectors
  • Serge Gaspers and Stefan Szeider. Backdoors to Acyclic SAT
  • Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese. Assigning Sporadic Tasks to Unrelated Parallel Machines
  • Artur Jeż. Faster fully compressed pattern matching by recompression
  • Ramanujan M. S. and Daniel Lokshtanov. Parameterized Tractability of Multiway Cut with Parity Constraints
  • Karl Bringmann and Konstantinos Panagiotou. Efficient Sampling Methods for Discrete Distributions
  • Robert Crowston, Mark Jones and Matthias Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound
  • Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs
  • Moses Charikar and Shi Li. A Dependent LP-rounding Approach for the $k$-Median Problem
  • Loukas Georgiadis and Robert Tarjan. Dominators, Directed Bipolar Orders, and Independent Spanning Trees
  • Chandra Chekuri, Alina Ene and Ali Vakilian. Node-weighted Network Design in Planar and Minor-closed Families of Graphs
  • Anindya De, Ilias Diakonikolas and Rocco Servedio. The Inverse Shapley Value Problem
  • Arash Farzan, Ian Munro and Rajeev Raman. Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
  • Michael Rabin, Yishay Mansour, Muthu Muthuikrishnan and Moti Yung. Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
  • Siddharth Barman, Shuchi Chawla, David Malec and Seeun Umboh. Secretary Problems with Convex Costs
  • Michael Kapralov and Rina Panigrahy. NNS lower bounds via metric expansion for $l_\infty$ and $EMD$
  • Rahul Santhanam and Srikanth Srinivasan. On the Limits of Sparsification
  • Matthew Patitz, Robert Schweller, Bin Fu and Robert Sheline. Self-Assembly with Geometric Tiles
  • Barna Saha and Samir Khuller. Set Cover Revisited: Hypergraph Cover with Hard Capacities
  • Yaoyun Shi and Xiaodi Wu. Epsilon-net method for optimizations over separable states
  • Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan. Quadratic Programming with a Ratio Objective
  • Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
  • Jaroslaw Byrka and Bartosz Rybicki. Improved LP-rounding approximation algorithm for $k$-level uncapacitated facility location
  • Philip Klein and Dániel Marx. Solving planar $k$-terminal cut in $O(n^{c \sqrt{k}})$ time
  • Anupam Gupta and Kevin Lewi. The Online Metric Matching Problem for Doubling Metrics
  • Dimitris Achlioptas and Ricardo Menchaca-Mendez. Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method
  • Kousha Etessami, Alistair Stewart and Mihalis Yannakakis. Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
  • Prosenjit Bose, Sebastien Collette, Rolf Fagerberg and Stefan Langerman. De-amortizing Binary Search Trees
  • Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen. The NOF Multiparty Communication Complexity of Composed Functions
  • Justin Thaler, Jonathan Ullman and Salil Vadhan. Faster Algorithms for Privately Releasing Marginals