default search action
42nd ICALP 2015: Kyoto, Japan - Part I
- Magnús M. Halldórsson
, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. Lecture Notes in Computer Science 9134, Springer 2015, ISBN 978-3-662-47671-0 - Shweta Agrawal, Yuval Ishai, Dakshita Khurana, Anat Paskin-Cherniavsky:
Statistical Randomized Encodings: A Complexity Theoretic View. 1-13 - Nir Ailon:
Tighter Fourier Transform Lower Bounds. 14-25 - Susanne Albers, Dario Frascaria:
Quantifying Competitiveness in Paging with Locality of Reference. 26-38 - Georgios Amanatidis
Approximation Algorithms for Computing Maximin Share Allocations. 39-51 - Elliot Anshelevich
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare. 52-64 - Boris Aronov
Batched Point Location in SINR Diagrams via Algebraic Tools. 65-77 - Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, Yuval Rabani
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs. 78-90 - Yossi Azar, Ilan Reuven Cohen:
Serving in the Dark should be done Non-Uniformly. 91-102 - Paul Beame, Vincent Liew, Mihai Patrascu:
Finding the Median (Obliviously) with Bounded Space. 103-115 - Babak Behsaz, Zachary Friggstad, Mohammad R. Salavatipour, Rohit Sivakumar:
Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median. 116-128 - Xiaohui Bei
Solving Linear Programming with Constraints Unknown. 129-142 - Salman Beigi, Omid Etesami, Amin Gohari
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. 143-154 - Christoph Berkholz, Martin Grohe
Limitations of Algebraic Approaches to Graph Isomorphism Testing. 155-166 - Aaron Bernstein, Cliff Stein:
Fully Dynamic Matching in Bipartite Graphs. 167-179 - Olaf Beyersdorff
Feasible Interpolation for QBF Resolution Calculi. 180-192 - Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Simultaneous Approximation of Constraint Satisfaction Problems. 193-205 - Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
Design of Dynamic Algorithms via Primal-Dual Method. 206-218 - Laurent Bienvenu, Damien Desfontaines, Alexander Shen
What Percentage of Programs Halt? 219-230 - Andreas Björklund, Holger Dell, Thore Husfeldt:
The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems. 231-242 - Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
Spotting Trees with Few Leaves. 243-255 - Manuel Bodirsky
Constraint Satisfaction Problems over the Integers with Successor. 256-267 - Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. 268-280 - Benjamin A. Burton
Algorithms and Complexity for Turaev-Viro Invariants. 281-293 - Clément L. Canonne:
Big Data on the Rise? - Testing Monotonicity of Distributions. 294-305 - Yixin Cao
Unit Interval Editing is Fixed-Parameter Tractable. 306-317 - Chandra Chekuri, Shalmoli Gupta, Kent Quanrud:
Streaming Algorithms for Submodular Function Maximization. 318-330 - Aloni Cohen, Justin Holmgren:
Multilinear Pseudorandom Functions. 331-342 - Gil Cohen, Igor Shinkar:
Zero-Fixing Extractors for Sub-Logarithmic Entropy. 343-354 - Matthew Coudron, Thomas Vidick
Interactive Proofs with Approximately Commuting Provers. 355-366 - Ágnes Cseh, Chien-Chung Huang, Telikepalli Kavitha:
Popular Matchings with Two-Sided Preferences and One-Sided Ties. 367-379 - Radu Curticapean:
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity. 380-392 - Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols. 393-405 - Yann Disser, Max Klimm, Elisabeth Lübbecke:
Scheduling Bidirectional Traffic on a Path. 406-418 - Dean Doron, Amnon Ta-Shma
On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace. 419-431 - Zdenek Dvorák
On Planar Boolean CSP. 432-443 - Thomas Erlebach, Michael Hoffmann, Frank Kammer:
On Temporal Graph Exploration. 444-455 - Antonio Faonio
Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation. 456-468 - Andreas Emil Feldmann
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. 469-480 - Fedor V. Fomin
Lower Bounds for the Graph Homomorphism Problem. 481-493 - Fedor V. Fomin
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. 494-505 - Lila Fontes, Rahul Jain
Relative Discrepancy Does not Separate Information and Communication Complexity. 506-516 - Peter Fulla, Stanislav Zivný:
A Galois Connection for Valued Constraint Languages of Infinite Size. 517-528 - Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum:
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. 529-541 - Sumit Ganguly:
Taylor Polynomial Estimator for Estimating Frequency Moments. 542-553 - Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod:
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria. 554-566 - Serge Gaspers, Gregory B. Sorkin
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. 567-579 - Pawel Gawrychowski, Shay Mozes
Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search. 580-592 - Pawel Gawrychowski, Patrick K. Nicholson:
Optimal Encodings for Range Top- k k , Selection, and Min-Max. 593-604 - Loukas Georgiadis
2-Vertex Connectivity in Directed Graphs. 605-616 - Sevag Gharibian, Jamie Sikora:
Ground State Connectivity of Local Hamiltonians. 617-628 - Archontia C. Giannopoulou
Uniform Kernelization Complexity of Hitting Forbidden Minors. 629-641 - Andreas Göbel, Leslie Ann Goldberg, David Richerby
Counting Homomorphisms to Square-Free Graphs, Modulo 2. 642-653 - Leslie Ann Goldberg, Rob Gysel, John Lapinskas
Approximately Counting Locally-Optimal Structures. 654-665 - Oded Goldreich
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). 666-677 - Ulrike Große, Joachim Gudmundsson
Fast Algorithms for Diameter-Optimally Augmenting Paths. 678-688 - Thomas Dueholm Hansen, Haim Kaplan, Robert Endre Tarjan, Uri Zwick
Hollow Heaps. 689-700 - Brett Hemenway, Mary Wootters:
Linear-Time List Recovery of High-Rate Expander Codes. 701-712 - Monika Henzinger, Sebastian Krinninger
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. 713-724 - Monika Henzinger, Sebastian Krinninger
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. 725-736 - Sungjin Im, Benjamin Moseley:
Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities. 737-748 - Hamid Jahanjou, Eric Miles, Emanuele Viola:
Local Reductions. 749-760 - Jedrzej Kaniewski
Query Complexity in Expectation. 761-772 - Sampath Kannan, Claire Mathieu, Hang Zhou:
Near-Linear Query Complexity for Graph Inference. 773-784 - Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu:
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. 785-796 - Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden. 797-809 - Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha:
Lower Bounds for Sums of Powers of Low Degree Univariates. 810-821 - Subhash Khot, Rishi Saket:
Approximating CSPs Using LP Relaxation. 822-833 - Balagopal Komarath, Jayalal Sarma, K. S. Sunil:
Comparator Circuits over Finite Bounded Posets. 834-845 - Marcin Kozik, Joanna Ochremiak:
Algebraic Properties of Valued Constraint Satisfaction Problem. 846-858 - Marvin Künnemann, Bodo Manthey:
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. 859-871 - Adam Kurpisz
On the Hardest Problem Formulations for the 0/1 0 / 1 Lasserre Hierarchy. 872-885 - Jerry Li, John Peebles:
Replacing Mark Bits with Randomness in Fibonacci Heaps. 886-897 - Jian Li, Yifei Jin:
A PTAS for the Weighted Unit Disk Cover Problem. 898-909 - Lingxiao Huang
Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points. 910-921 - Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan
Deterministic Truncation of Linear Matroids. 922-934 - Daniel Lokshtanov, M. S. Ramanujan
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. 935-946 - Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang:
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. 947-959 - Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. 960-972 - Tobias Mömke, Andreas Wiese:
A (2+\epsilon ) ( 2 + ϵ ) -Approximation Algorithm for the Storage Allocation Problem. 973-984 - Amer E. Mouawad
Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas. 985-996 - Amir Nayyeri, Anastasios Sidiropoulos:
Computing the Fréchet Distance Between Polygons with Holes. 997-1009 - Aleksandar Nikolov
An Improved Private Mechanism for Small Databases. 1010-1021 - Lila Kari, Steffen Kopecki, Pierre-Étienne Meunier, Matthew J. Patitz
Binary Pattern Tile Set Synthesis Is NP-hard. 1022-1034 - Swagato Sanyal:
Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity. 1035-1045 - Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak:
Condensed Unpredictability. 1046-1057 - Johan Thapper
Sherali-Adams Relaxations for Valued CSPs. 1058-1069 - Yajun Wang, Sam Chiu-wai Wong:
Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm. 1070-1081 - Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. 1082-1093 - Huacheng Yu:
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. 1094-1105
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 2025-11-14 22:25 CET 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: