Accepted Papers
by
Michael Hoffmann
—
last modified
Apr 13, 2011 09:02 AM
The following contributions have been accepted for presentation at ICALP 2011. They are listed in no particular order.
There is also a list including abstracts.
- A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
- Fast Convergence for Consensus in Dynamic Networks
- On variants of file caching
- Constraint satisfaction parameterized by solution size
- Vertex Cover in Graphs with Locally Few Colors
- Efficient Sample Extractors for Juntas with Applications
- Content Search Through Comparisons
- Nondeterminism is Essential in Small 2FAs with Few Reversals
- Center stable matchings and centers of cover graphs of distributive lattices
- Limitations on quantum dimensionality reduction
- Efficient Distributed Communication in Ad-hoc Radio Networks
- On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
- On the power of lower bound methods for one-way quantum communication complexity
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Fault-Tolerant Compact Routing Schemes for General Graphs
- Popular Matchings in the Stable Marriage Problem
- An O(log n)-competitive algorithm for online constrained forest problems
- Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
- Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation
- Clustering with Local Restrictions
- The decimation process in random k-SAT
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- On Stabilization in Herman's Algorithm
- An improved approximation algorithm for the minimum-cost subset k-connectivity
- Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
- Algebraic Independence and Blackbox Identity Testing
- Robust Independence Systems
- Programming with Infinitesimals: A While-Language for Hybrid System Modeling
- Runtime Analysis of Probabilistic Programs with Unbounded Recursion
- Subset Feedback Vertex Set is Fixed Parameter Tractable
- Generic Expression Hardness Results for Primitive Positive Formula Comparison
- Local Matching Dynamics in Social Networks
- On the power of algebraic branching programs of width two
- Adaptively Secure Non-Interactive Threshold Cryptosystems
- A 1.488-approximation algorithm for the uncapacitated facility location problem
- Online Graph Exploration: New Results on Old and New Algorithms
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
- Pairwise-interaction Games
- Clique Clustering yields a PTAS for max-Coloring Interval Graphs
- Isomorphism of regular trees and words
- Collusion in Atomic Splittable Routing Games
- Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
- A Tighter Insertion-based Approximation of the Crossing Number
- Rice's theorem for mu-limit sets of cellular automata
- On the Advice Complexity of the k-Server Problem
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model
- Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
- A Fragment of ML Decidable by Visibly Pushdown Automata
- Submodular Cost Allocation Problem and Applications
- Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
- Existence and uniqueness of equilibria for flows over time
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
- Player-Centric Byzantine Agreement
- Maximizing a Polynomial Subject to Assignment Constraints
- Domination when the Stars Are Out
- VC-Dimension and Shortest Path Algorithms
- Tight Bounds for Linkages in Planar Graphs
- Regular Languages of Words Over Countable Linear Orderings
- Guarded negation
- The Complexity of Symmetric Boolean Parity Holant Problems
- New Algorithms for Learning in Presence of Errors
- Compact Navigation and Distance Oracles for Graphs with Small Treewidth
- Buyback Problem - Approximate matroid intersection with cancellation costs
- Meeting deadlines: How much speed suffices?
- Locality of queries definable in invariant first-order logic with arbitrary built-in predicates
- Recoverable Values for Independent Sets
- Distance Oracles for Vertex-Labeled Graphs
- Linear Programming and Combinatorial Bounds on Steiner Transitive-Closure Spanners
- Sorting by Transpositions is Difficult
- Relating Computational Effects by TT-Lifting
- Constructing differential categories and deconstructing categories of games
- Modular Markovian Logic
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Settling the complexity of local max-cut (almost) completely
- On the capabilities of grammars, automata, and transducers controlled by monoids
- Emptiness and Universality Problems in Timed Automata with Positive Frequency
- Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
- Automatizability and Simple Stochastic Games
- Automata-based CSL model checking
- On Tree-Constrained Matchings and Generalizations
- Convergence Time of Power Control Dynamics
- The cost of traveling between languages
- Liveness-preserving atomicity abstraction
- Parameterized Bounded-Depth Frege is Not Optimal
- Range Majority in Constant Time and Linear Space
- On Reachability for Hybrid Automata over Bounded Time
- Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
- Advice Coins for Classical and Quantum Computation
- Sleep Management on Multiple Machines for Energy and Flow Time
- Multiply-Recursive Upper Bounds with Higman’s Lemma
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
- Robust Simulations and Significant Separations
- The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
- Improved bounds for the randomized decision tree complexity of recursive majority
- Buechi Automata can have Smaller Quotients
- On the Semantics of Markov Automata
- Quantum Commitments from Complexity Assumptions
- Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience
- Krivine machines and higher-order schemes
- Asymptotically Optimal Randomized Rumor Spreading
- Limits on the Computational Power of Random Strings
- A new Approach for Analyzing Convergence Algorithms for Mobile Robots
- Deciding robustness against total store ordering
- Restoring Pure Equilibria to Weighted Congestion Games
- Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems
- Dynamic Planar Range Maxima Queries
- Approximating the Termination Value of One-counter MDPs and Stochastic Games
- Approximation schemes for capacitated geometric network design
- Improved Approximation for the Directed Spanner Problem
- Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
- A PCP Characterization of AM
- A Progress Measure for Explicit-State Probabilistic Model-Checkers
Program is available.
