default search action
41st ICALP 2014: Copenhagen, Denmark - Part I
- Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias:
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Lecture Notes in Computer Science 8572, Springer 2014, ISBN 978-3-662-43947-0
Invited Talks
- Eli Gafni, Maurice Herlihy:
Sporadic Solutions to Zero-One Exclusion Tasks. 1-10 - Viktor Kuncak:
Verifying and Synthesizing Software with Recursive Functions - (Invited Contribution). 11-25
Track A: Algorithms, Complexity, and Games
- Scott Aaronson, Andris Ambainis, Kaspars Balodis
, Mohammad Bavarian:
Weak Parity. 26-38 - Amir Abboud, Virginia Vassilevska Williams, Oren Weimann
Consequences of Faster Alignment of Sequences. 39-51 - Ittai Abraham, Shiri Chechik:
Distance Labels with Optimal Local Stretch. 52-63 - David Adjiashvili, Sandro Bosio, Robert Weismantel, Rico Zenklusen:
Time-Expanded Packings. 64-76 - Peyman Afshani, Timothy M. Chan, Konstantinos Tsakalidis:
Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM. 77-88 - Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert:
The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average. 89-100 - Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations between Sensitivity and Other Complexity Measures. 101-113 - Amihood Amir, Timothy M. Chan, Moshe Lewenstein, Noa Lewenstein:
On Hardness of Jumbled Indexing. 114-125 - Patrizio Angelini
Morphing Planar Graph Drawings Optimally. 126-137 - Surender Baswana, Shahbaz Khan
Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs. 138-149 - Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito:
On the Role of Shared Randomness in Simultaneous Communication. 150-162 - Eli Ben-Sasson, Emanuele Viola:
Short PCPs with Projection Queries. 163-173 - René van Bevern, Robert Bredereck, Laurent Bulteau
Star Partitions of Perfect Graphs. 174-185 - Sayan Bhattacharya, Janardhan Kulkarni, Vahab S. Mirrokni:
Coordination Mechanisms for Selfish Routing over Time on a Tree. 186-197 - Therese Biedl:
On Area-Optimal Planar Graph Drawings. 198-210 - Andreas Björklund, Thore Husfeldt:
Shortest Two Disjoint Paths in Polynomial Time. 211-222 - Andreas Björklund, Rasmus Pagh
Listing Triangles. 223-234 - Eric Blais, Johan Håstad
On DNF Approximators for Monotone Boolean Functions. 235-246 - Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas:
Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract). 247-258 - Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf:
Lower Bounds for Approximate LDCs. 259-270 - Jin-Yi Cai, Heng Guo, Tyson Williams:
Holographic Algorithms Beyond Matchgates. 271-282 - Clément L. Canonne, Ronitt Rubinfeld:
Testing Probability Distributions Underlying Aggregated Data. 283-295 - André Chailloux, Giannicola Scarpa
Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost. 296-307 - Andrew M. Childs
The Bose-Hubbard Model is QMA-complete. 308-319 - Richard Cleve, Rajat Mittal:
Characterization of Binary Constraint System Games. 320-331 - Richard Cole, Howard J. Karloff:
Fast Algorithms for Constructing Maximum Entropy Summary Trees. 332-343 - Artur Czumaj, Berthold Vöcking:
Thorp Shuffling, Butterflies, and Non-Markovian Couplings. 344-355 - Samir Datta
Dynamic Complexity of Directed Reachability and Other Problems. 356-367 - Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile. 368-379 - Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane
Canadians Should Travel Randomly. 380-391 - Shahar Dobzinski, Renato Paes Leme:
Efficiency Guarantees in Auctions with Budgets. 392-404 - Markus Sortland Dregi, Daniel Lokshtanov:
Parameterized Complexity of Bandwidth on Trees. 405-416 - Zeev Dvir, Rafael Oliveira, Amir Shpilka
Testing Equivalence of Polynomials under Shifts. 417-428 - György Dósa, Jirí Sgall
Optimal Analysis of Best Fit Bin Packing. 429-441 - Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. 442-452 - Yuval Emek, Adi Rosén:
Semi-Streaming Set Cover - (Extended Abstract). 453-464 - Hossein Esfandiari, MohammadTaghi Hajiaghayi, Mohammad Reza Khani, Vahid Liaghat, Hamid Mahini, Harald Räcke:
Online Stochastic Reordering Buffer Scheduling. 465-476 - Uriel Feige, Shlomo Jozeph:
Demand Queries with Preprocessing. 477-488 - Jirí Fiala, Pavel Klavík
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs. 489-501 - Mark Braverman, Ankit Garg:
Public vs Private Coin in Bounded-Round Information. 502-513 - Dmitry Gavinsky, Shachar Lovett
En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. 514-524 - Pawel Gawrychowski, Shay Mozes
Improved Submatrix Maximum Queries in Monge Matrices. 525-537 - Anna C. Gilbert, Yi Li
For-All Sparse Recovery in Near-Optimal Time. 538-550 - Alexander Golovnev, Alexander S. Kulikov
Families with Infants: A General Approach to Solve Hard Partition Problems. 551-562 - Anupam Gupta, Kunal Talwar, Udi Wieder:
Changing Bases: Multistage Optimization for Matroids and Matchings. 563-575 - MohammadTaghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi:
Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems. 576-587 - Chinmay Hegde, Piotr Indyk, Ludwig Schmidt:
Nearly Linear-Time Model-Based Compressive Sensing. 588-599 - Timon Hertli:
Breaking the PPSZ Barrier for Unique 3-SAT. 600-611 - Justin Hsu
Privately Solving Linear Programs. 612-624 - Wiebke Höhn, Julián Mestre, Andreas Wiese
How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions. 625-636 - John Iacono, Özgür Özkan:
Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not. 637-649 - Yuval Ishai, Hoeteck Wee:
Partial Garbling Schemes and Their Applications. 650-662 - Gábor Ivanyos
On the Complexity of Trial and Error for Constraint Satisfaction Problems. 663-675 - Sune K. Jakobsen:
Information Theoretical Cryptogenography. 676-688 - Subhash Khot, Madhur Tulsiani, Pratik Worah
The Complexity of Somewhat Approximation Resistant Predicates. 689-700 - Gillat Kol, Shay Moran, Amir Shpilka
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound. 701-712 - Spyros C. Kontogiannis
Distance Oracles for Time-Dependent Networks. 713-725 - Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. 726-737 - Tomasz Krawczyk, Bartosz Walczak
Coloring Relatives of Interval Overlap Graphs via On-line Games. 738-750 - Mrinal Kumar, Shubhangi Saraf:
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits. 751-762 - Mitsuru Kusumoto, Yuichi Yoshida:
Testing Forest-Isomorphism in the Adjacency List Model. 763-774 - Michael Lampis:
Parameterized Approximation Schemes Using Graph Widths. 775-786 - Pinyan Lu
FPTAS for Weighted Fibonacci Gates and Its Applications. 787-799 - Manu Basavaraju, Fedor V. Fomin
Parameterized Algorithms to Preserve Connectivity. 800-811 - Konstantin Makarychev, Yury Makarychev:
Nonuniform Graph Partitioning with Unrelated Weights. 812-822 - Konstantin Makarychev, Debmalya Panigrahi:
Precedence-Constrained Scheduling of Malleable Jobs with Preemption. 823-834 - Laura Mancinska, Thomas Vidick
Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. 835-846 - Petar Dapic
QCSP on Semicomplete Digraphs. 847-858 - Raghu Meka, Omer Reingold, Guy N. Rothblum, Ron D. Rothblum:
Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract). 859-870 - George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:
Determining Majority in Networks with Local Interactions and Very Small Local Memory. 871-882 - Jelani Nelson, Huy L. Nguyên:
Lower Bounds for Oblivious Subspace Embeddings. 883-894 - Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:
On Input Indistinguishable Proof Systems. 895-906 - Manoj Prabhakaran, Amit Sahai, Akshay Wadia:
Secure Computation Using Leaky Tokens. 907-918 - Hartmut Klauck
An Improved Interactive Streaming Algorithm for the Distinct Elements Problem. 919-930 - Felix Reidl
A Faster Parameterized Algorithm for Treedepth. 931-942 - Omer Reingold, Ron D. Rothblum, Udi Wieder:
Pseudorandom Graphs in Data Structures. 943-954 - Eli Ben-Sasson, Noga Ron-Zewi
Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. 955-966 - Jens M. Schmidt
The Mondshein Sequence. 967-978 - Kunal Talwar, Udi Wieder:
Balanced Allocations: A Simple Proof for the Heavily Loaded Case. 979-990 - Pierre-Alain Fouque
Close to Uniform Prime Number Generation with Fewer Random Bits. 991-1002 - Madhur Tulsiani, John Wright, Yuan Zhou:
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. 1003-1014 - Iddo Tzameret:
Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem - (Extended Abstract). 1015-1026 - Ilya Volkovich
On Learning, Lower Bounds and (un)Keeping Promises. 1027-1038 - Yaoyu Wang, Yitong Yin:
Certificates in Data Structures. 1039-1050 - Karl Wimmer, Yi Wu, Peng Zhang:
Optimal Query Complexity for Estimating the Trace of a Matrix. 1051-1062 - Christian Wulff-Nilsen:
Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles. 1063-1074 - Yitong Yin:
Spatial Mixing of Coloring Random Graphs. 1075-1086
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-10-04 19:48 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: