Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, Roger Wattenhofer
Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Part I
ICALP (1), 2012.

@proceedings{ICALP-v1-2012,
	address       = "Warwick, United Kingdom",
	doi           = "10.1007/978-3-642-31594-7",
	editor        = "Artur Czumaj and Kurt Mehlhorn and Andrew M. Pitts and Roger Wattenhofer",
	isbn          = "978-3-642-31593-0",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Part I}",
	volume        = 7391,
	year          = 2012,
}

Contents (71 items)

8 ×#approximate
7 ×#algorithm
7 ×#bound
7 ×#problem
6 ×#complexity
6 ×#online
5 ×#graph
5 ×#multi
5 ×#performance
5 ×#quantum

ICALP-v1-2012-AchlioptasM #bound #random #satisfiability

Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method (DA, RMM), pp. 1–12.

ICALP-v1-2012-AdaCFN #communication #complexity #multi

The NOF Multiparty Communication Complexity of Composed Functions (AA, AC, OF, PN), pp. 13–24.

ICALP-v1-2012-AmbainisBBKOSV #game studies #quantum

Quantum Strategies Are Better Than Classical in Almost Any XOR Game (AA, AB, KB, DK, RO, JS, MV), pp. 25–37.

ICALP-v1-2012-AzarG #constraints #linear #performance

Efficient Submodular Function Maximization under Linear Packing Constraints (YA, IG), pp. 38–50.

ICALP-v1-2012-BabaiCQ #morphism #polynomial

Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups — (LB, PC, YQ), pp. 51–62.

ICALP-v1-2012-BalcanL #clustering

Clustering under Perturbation Resilience (MFB, YL), pp. 63–74.

ICALP-v1-2012-BarmanUCM #problem

Secretary Problems with Convex Costs (SB, SU, SC, DLM), pp. 75–87.

ICALP-v1-2012-BaronOV #black box

Nearly Simultaneously Resettable Black-Box Zero Knowledge (JB, RO, IV), pp. 88–99.

ICALP-v1-2012-Bauwens #complexity

Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity (BB), pp. 100–108.

ICALP-v1-2012-BhaskaraCMV #on the #polynomial #programming

On Quadratic Programming with a Ratio Objective (AB, MC, RM, AV), pp. 109–120.

ICALP-v1-2012-BoseCFL

De-amortizing Binary Search Trees (PB, SC, RF, SL), pp. 121–132.

ICALP-v1-2012-BringmannP #performance

Efficient Sampling Methods for Discrete Distributions (KB, KP), pp. 133–144.

ICALP-v1-2012-BuchbinderNRS #algorithm #approximate #constraints #online #rank

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints (NB, JN, RR, MS), pp. 145–156.

ICALP-v1-2012-ByrkaR #algorithm #approximate

Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location (JB, BR), pp. 157–169.

ICALP-v1-2012-ChakrabartyH #testing

Testing Coverage Functions (DC, ZH), pp. 170–181.

ICALP-v1-2012-ChanLN #bound #fault tolerance #metric

Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree (THHC, ML, LN), pp. 182–193.

ICALP-v1-2012-CharikarL #approach #problem

A Dependent LP-Rounding Approach for the k-Median Problem (MC, SL), pp. 194–205.

ICALP-v1-2012-ChekuriEV #design #graph #network #product line

Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs (CC, AE, AV), pp. 206–217.

ICALP-v1-2012-ChenW

Computing the Visibility Polygon of an Island in a Polygonal Domain (DZC, HW), pp. 218–229.

ICALP-v1-2012-ChitnisCHM #feedback #parametricity #set

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable (RHC, MC, MTH, DM), pp. 230–241.

ICALP-v1-2012-CrowstonJM #bound

Max-Cut Parameterized above the Edwards-Erdős Bound (RC, MJ, MM), pp. 242–253.

ICALP-v1-2012-CyganKPPW #clique #graph

Clique Cover and Graph Separation: New Incompressibility Results (MC, SK, MP, MP, MW), pp. 254–265.

ICALP-v1-2012-DeDS #problem

The Inverse Shapley Value Problem (AD, ID, RAS), pp. 266–277.

ICALP-v1-2012-DeshpandeKS

Zero-One Rounding of Singular Vectors (AD, RK, NS), pp. 278–289.

ICALP-v1-2012-DinitzKR #approximate #scalability

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner (MD, GK, RR), pp. 290–301.

ICALP-v1-2012-EmekHR

Space-Constrained Interval Selection (YE, MMH, AR), pp. 302–313.

ICALP-v1-2012-EtessamiSY #algorithm #branch #equation #markov #polynomial #probability #process

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations (KE, AS, MY), pp. 314–326.

ICALP-v1-2012-FarzanMR #orthogonal #query

Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima (AF, JIM, RR), pp. 327–338.

ICALP-v1-2012-FeigeJ #graph

Universal Factor Graphs (UF, SJ), pp. 339–350.

ICALP-v1-2012-FellowsKRS #approximate

Parameterized Approximation via Fidelity Preserving Transformations (MRF, AK, FAR, HS), pp. 351–362.

ICALP-v1-2012-GaspersS #satisfiability

Backdoors to Acyclic SAT (SG, SS), pp. 363–374.

ICALP-v1-2012-GeorgiadisT #independence #order

Dominators, Directed Bipolar Orders, and Independent Spanning Trees (LG, RET), pp. 375–386.

ICALP-v1-2012-GharibianK #approximate #problem #quantum

Hardness of Approximation for Quantum Problems (SG, JK), pp. 387–398.

ICALP-v1-2012-GoldbergJ #approximate #complexity #polynomial

The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) (LAG, MJ), pp. 399–410.

ICALP-v1-2012-GortzNS #probability

Stochastic Vehicle Routing with Recourse (ILG, VN, RS), pp. 411–423.

ICALP-v1-2012-GuptaL #metric #online #problem

The Online Metric Matching Problem for Doubling Metrics (AG, KL), pp. 424–435.

ICALP-v1-2012-GuptaN #approximate #integer #online #source code

Approximating Sparse Covering Integer Programs Online (AG, VN), pp. 436–448.

ICALP-v1-2012-HalldorssonSSW #approximate #clique #communication #complexity #streaming

Streaming and Communication Complexity of Clique Approximation (MMH, XS, MS, CW), pp. 449–460.

ICALP-v1-2012-HsuKR #distributed

Distributed Private Heavy Hitters (JH, SK, AR), pp. 461–472.

ICALP-v1-2012-HughesPRS #problem

A Thirty Year Old Conjecture about Promise Problems (AH, AP, NR, ALS), pp. 473–484.

ICALP-v1-2012-ImNZ #latency

Minimum Latency Submodular Cover (SI, VN, RvdZ), pp. 485–497.

ICALP-v1-2012-ItoTY #algorithm

Constant-Time Algorithms for Sparsity Matroids (HI, SiT, YY), pp. 498–509.

ICALP-v1-2012-JanssonSS #memory management #named #random

CRAM: Compressed Random Access Memory (JJ, KS, WKS), pp. 510–521.

ICALP-v1-2012-JefferyKM #complexity #graph #matrix #multi #quantum #query #using

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (SJ, RK, FM), pp. 522–532.

ICALP-v1-2012-Jez #pattern matching #performance

Faster Fully Compressed Pattern Matching by Recompression (AJ), pp. 533–544.

ICALP-v1-2012-KapralovP #bound #metric

NNS Lower Bounds via Metric Expansion for l ∞ and EMD (MK, RP), pp. 545–556.

ICALP-v1-2012-Kimmel #bound #quantum

Quantum Adversary (Upper) Bound (SK), pp. 557–568.

ICALP-v1-2012-KleinM

Solving Planar k-Terminal Cut in $O(n^(c√k)) Time (PNK, DM), pp. 569–580.

ICALP-v1-2012-KratschPPW #graph #multi #parametricity

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs (SK, MP, MP, MW), pp. 581–593.

ICALP-v1-2012-KrauthgamerZ #using

Preserving Terminal Distances Using Minors (RK, TZ), pp. 594–605.

ICALP-v1-2012-LaekhanukitGS #approach #problem

A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem (BL, SOG, MS), pp. 606–616.

ICALP-v1-2012-LaplanteLR #bound #detection #quantum

Classical and Quantum Partition Bound and Detector Inefficiency (SL, VL, JR), pp. 617–628.

ICALP-v1-2012-LeviRR #testing

Testing Similar Means (RL, DR, RR), pp. 629–640.

ICALP-v1-2012-LinC #complexity

The Parameterized Complexity of k-Edge Induced Subgraphs (BL, YC), pp. 641–652.

ICALP-v1-2012-MansourRVX #algorithm #online

Converting Online Algorithms to Local Computation Algorithms (YM, AR, SV, NX), pp. 653–664.

ICALP-v1-2012-Marchetti-SpaccamelaRSW #parallel

Assigning Sporadic Tasks to Unrelated Parallel Machines (AMS, CR, SvdS, AW), pp. 665–676.

ICALP-v1-2012-Marx #bound #multi

A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals (DM), pp. 677–688.

ICALP-v1-2012-MegowSVW #online #power of

The Power of Recourse for Online MST and TSP (NM, MS, JV, AW), pp. 689–700.

ICALP-v1-2012-MolinaroR #geometry #linear #online #source code

Geometry of Online Packing Linear Programs (MM, RR), pp. 701–713.

ICALP-v1-2012-FuPSS #geometry #self

Self-assembly with Geometric Tiles (BF, MJP, RTS, RS), pp. 714–725.

ICALP-v1-2012-PolacekS #strict

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation (LP, OS), pp. 726–737.

ICALP-v1-2012-RabinMMY #performance #strict #transaction #validation

Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions (MOR, YM, SM, MY), pp. 738–749.

ICALP-v1-2012-LokshtanovR #constraints #multi

Parameterized Tractability of Multiway Cut with Parity Constraints (DL, MSR), pp. 750–761.

ICALP-v1-2012-SahaK #set

Set Cover Revisited: Hypergraph Cover with Hard Capacities (BS, SK), pp. 762–773.

ICALP-v1-2012-SanthanamS #on the

On the Limits of Sparsification (RS, SS), pp. 774–785.

ICALP-v1-2012-Schmidt #linear

Certifying 3-Connectivity in Linear Time (JMS), pp. 786–797.

ICALP-v1-2012-ShiW #optimisation

Epsilon-Net Method for Optimizations over Separable States (YS, XW), pp. 798–809.

ICALP-v1-2012-ThalerUV #algorithm #performance

Faster Algorithms for Privately Releasing Marginals (JT, JU, SPV), pp. 810–821.

ICALP-v1-2012-CostelloTT #probability

Stochastic Matching with Commitment (KPC, PT, PT), pp. 822–833.

ICALP-v1-2012-VerbinZ #distance #named #sketching

Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance (EV, QZ), pp. 834–845.

ICALP-v1-2012-Zouzias #algorithm #matrix

A Matrix Hyperbolic Cosine Algorithm and Applications (AZ), pp. 846–858.