Search ACM DL

Search Issue

enter search term and/or author name

**Testing Properties of Sparse Images**

Dana Ron, Gilad Tsur

Article No.: 17

DOI: 10.1145/2635806

We initiate the study of testing properties of images that correspond to *sparse* 0/1-valued matrices of size *n*× *n*. Our study is related to but different from the study initiated by Raskhodnikova (*Proceedings of RANDOM,...
*

*
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
Article No.: 18
DOI: 10.1145/2629672
*

*We show that for every positive ϵ > 0, unless NP ⊂ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2 ^{log1-ϵ n} by a reduction from the maximum...
*

*
Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem
Stefan Kratsch
Article No.: 19
DOI: 10.1145/2635808
*

*The field of kernelization offers a rigorous way of studying the ubiquitous technique of data reduction and preprocessing for combinatorially hard problems. A widely accepted definition of useful data reduction is that of a polynomial...
*

*
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
Stefan Kratsch, Magnus Wahlström
Article No.: 20
DOI: 10.1145/2635810
*

*The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a...
*

*
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlén
Article No.: 21
DOI: 10.1145/2635812
*

*We show conditional lower bounds for well-studied #P-hard problems:*

The number of satisfying assignments of a 2-CNF formula with *n* variables cannot be computed in time exp(*o*(*n*)), and the same is true for computing...

**Real-Time Streaming String-Matching**

Dany Breslauer, Zvi Galil

Article No.: 22

DOI: 10.1145/2635814

This article presents a real-time randomized streaming string-matching algorithm that uses *O*(log *m*) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the...

**Alphabet-Independent Compressed Text Indexing**

Djamal Belazzougui, Gonzalo Navarro

Article No.: 23

DOI: 10.1145/2635816

Self-indexes are able to represent a text asymptotically within the information-theoretic lower bound under the *k*th order entropy model and offer access to any text substring and indexed pattern searches. Their time complexities are not...

**Principles of Robust Medium Access and an Application to Leader Election**

Baruch Awerbuch, Andrea Richa, Christian Scheideler, Stefan Schmid, Jin Zhang

Article No.: 24

DOI: 10.1145/2635818

This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or...