ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 64 Issue 2, May 2017



Section: Design 8 Analysis of Algorithms and/or Randomness

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Article No.: 8
DOI: 10.1145/3046674

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is...

Section: Design 8 Analysis of Algorithms and/or Randomness

Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman, Alistair Sinclair
Article No.: 9
DOI: 10.1145/2988227

We study a classical iterative algorithm for balancing matrices in the L norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett 8 Reinsch in the 1960s, is implemented as a standard...

Section: Design 8 Analysis of Algorithms and/or Randomness

Arithmetic Cryptography
Benny Applebaum, Jonathan Avron, Chris Brzuska
Article No.: 10
DOI: 10.1145/3046675

We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field...

Section: Design 8 Analysis of Algorithms and/or Randomness

On the Switch Markov Chain for Perfect Matchings
Martin Dyer, Mark Jerrum, Haiko Müller
Article No.: 12
DOI: 10.1145/2822322

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. We ask:...

Section: Design 8 Analysis of Algorithms and/or Randomness

Monadic Decomposition
Margus Veanes, Nikolaj Bjørner, Lev Nachmanson, Sergey Bereg
Article No.: 14
DOI: 10.1145/3040488

Monadic predicates play a prominent role in many decidable cases, including decision procedures for symbolic automata. We are here interested in discovering whether a formula can be rewritten into a Boolean combination of monadic...

Section: Design 8 Analysis of Algorithms and/or Randomness

Verifying Increasingly Expressive Temporal Logics for Infinite-State Systems
Byron Cook, Heidy Khlaaf, Nir Piterman
Article No.: 15
DOI: 10.1145/3060257

Temporal logic is a formal system for specifying and reasoning about propositions qualified in terms of time. It offers a unified approach to program verification as it applies to both sequential and parallel programs and provides a uniform...