**Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem**by Thomas Watson

March 28, 2014.

We study the lift-and-project procedures of Lovasz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least $2$. We prove that after one round of the Lovasz-Schrijver or Sherali-Adams procedures, the integrality gap of the asymmetric TSP tour problem is at least $3/2$, with a caveat on which version of the standard relaxation is used. For the symmetric TSP tour problem, the integrality gap of the standard relaxation is known to be at least $4/3$, and Cheung (SIOPT 2005) proved that it remains at least $4/3$ after $o(n)$ rounds of the Lovasz-Schrijver procedure, where $n$ is the number of nodes. For the symmetric TSP path problem, the integrality gap of the standard relaxation is known to be at least $3/2$, and we prove that it remains at least $3/2$ after $o(n)$ rounds of the Lovasz-Schrijver procedure, by a simple reduction to Cheung's result.

**Reachability in $K_{3,3}$-free and $K_5$-free Graphs is in Unambiguous Logspace**by Thomas Thierauf and Fabian Wagner

April 14, 2014

We show that the reachability problem for directed graphs that are either $K_{3,3}$-free or $K_5$-free is in unambiguous log-space, $UL \cap coUL$. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in $UL \cap coUL$.

Our algorithm decomposes the graphs into biconnected and triconnected components. This gives a tree structure on these components. The non-planar components are replaced by planar components that maintain the reachability properties. For $K_5$-free graphs we also need a decomposition into 4-connected components. Thereby we provide a logspace reduction to the planar reachability problem.

We show the same upper bound for computing distances in $K_{3,3}$-free and $K_5$-free directed graphs and for computing longest paths in $K_{3,3}$-free and $K_5$-free directed acyclic graphs.

**Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction**by Mark Huber

June 8, 2014

A linear extension of a poset $([n],\preceq)$ is a permutation $\sigma$ such that if $\sigma(i) \preceq \sigma(j)$, then $i \leq j$. The problem considered here is sampling uniformly from the set of linear extensions. The best known algorithm for the general problem requires time $O(n^3\ln n)$. This work presents the first new method that is provably faster for a nontrivial class of posets. Specifically, when the poset is height-2 (so there do not exist distinct elements with $i \preceq j \preceq k$) and has bounded interaction (so for each $i$ there are at most $\Delta$ elements $i'$ with $i \preceq i'$ or $i' \preceq i$), then the new algorithm runs in time $O(n\Delta^2 \ln n)$. Such posets arise naturally as corrugated surfaces on graphs, where $\Delta - 1$ is the maximum degree of the graph. Therefore, finding corrugated surfaces on a fixed family of lattices takes $O(n \ln n)$ (near-linear time.) The ability to sample from the set of linear extensions can be used to build approximation algorithms for counting the number of linear extensions. Using the new method, an approximation scheme that counts the number of linear extensions to within a factor of $1 + \epsilon$ with fixed probability runs in $O(n^2 \Delta^2 [\ln n]^6\epsilon^{-2})$ time.

**Quantum Adversary Lower Bound for Element Distinctness with Small Range**by Ansis Rosmanis

July 10, 2014

The

*Element Distinctness*problem is to decide whether each character of an input string is unique. The quantum query complexity of*Element Distinctness*is known to be $\Theta(N^{2/3})$; the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size $\Omega(N^2)$.We construct a tight $\Omega(N^{2/3})$ adversary lower bound for

*Element Distinctness*with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.**Complexity of Testing Reachability in Matroids**by B. V. Raghavendra Rao and Jayalal Sarma

July 11, 2014

We extend the complexity theoretic framework of reachability problems in graphs to the case of matroids. Given a matroid $M$ and two elements $s$ and $t$ of the ground set, the reachability problem is to test if there is a circuit in $M$ containing both $s$ and $t$. We show complexity characterizations for several important classes of matroids. In particular, we show:

- For two important classes of matroids associated with graphs, namely, graphic and bi-circular matroids we show that the reachability problem is $\mathrm{L}$-complete.
- For transversal matroids, when a basis of $M$ is also given at the input, the problem can be shown to be $\mathrm{NL}$-complete. A general upper bound for this case is the complexity of constructing a matching ($\mathrm{RNC^2} \cap \mathrm{P}$).
- For linear matroids representable over $\mathbb{Q}$ and $\mathbb{Z}_\mathrm{p}$, we show that the problem characterizes $\mathrm{L}^{\mathrm{C = L}}$ and $\mathrm{Mod_p}\mathrm{L}$ respectively, which provides the first characterizations of these classes in terms of reachability problems.

**A composition theorem for decision tree complexity**by Ashley Montanaro

July 17, 2014

We completely characterise the complexity in the decision tree model of computing composite relations of the form $h = g \circ (f^1,\dots,f^n)$, where each relation $f^i$ is boolean-valued. Immediate corollaries include a direct sum theorem for decision tree complexity and a tight characterisation of the decision tree complexity of iterated boolean functions.

**Computing in Permutation Groups Without Memory**by Peter J. Cameron, Ben Fairbairn and Maxmilien Gadouleau

November 2, 2014

Memoryless computation is a modern technique to compute any function of a set of registers by updating one register at a time while using no memory. Its aim is to emulate how computations are performed in modern cores, since they typically involve updates of single registers. The memoryless computation model can be fully expressed in terms of transformation semigroups, or in the case of bijective functions, permutation groups. In this paper, we consider how efficiently permutations can be computed without memory. We determine the minimum number of basic updates required to compute any permutation, or any even permutation. The small number of required instructions shows that very small instruction sets could be encoded on cores to perform memoryless computation. We then start looking at a possible compromise between the size of the instruction set and the length of the resulting programs. We consider updates only involving a limited number of registers. In particular, we show that binary instructions are not enough to compute all permutations without memory when the alphabet size is even. These results, though expressed as properties of special generating sets of the symmetric or alternating groups, provide guidelines on the implementation of memoryless computation.

**Computing in Permutation Groups Without Memory**by Peter J. Cameron, Ben Fairbairn and Maxmilien Gadouleau

November 2, 2014

Memoryless computation is a novel means of computing any function of a set of registers by updating one register at a time while using no memory. We aim to emulate how computations are performed on modern cores, since they typically involve updates of single registers. The computation model of memoryless computation can be fully expressed in terms of transformation semigroups, or in the case of bijective functions, permutation groups. In this paper, we view registers as elements of a finite field and we compute linear permutation without memory. We first determine the maximum complexity of a linear function when only linear instructions are allowed. We also determine which linear functions are hardest to compute when the field in question is the binary field and the number of registers is even. Secondly, we investigate some matrix groups, thus showing that the special linear group is internally computable but not fast. Thirdly, we determine the smallest set of instructions required to generate the special and general linear groups. These results are important for memoryless computation, for they show that linear functions can be computed very fast or that very few instructions are needed to compute any linear function. They thus indicate new advantages of using memoryless computation.

**A Note on Subspace Evasive Sets**by Avraham Ben-Aroya, and Igor Shinkar

November 29, 2014

A subspace evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n\ $ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004) in the context of explicit constructions of Ramsey graphs. More recently, Guruswami (CCC 2011) showed that obtaining such sets over large fields can be used to construct capacity-achieving list-decodable codes with a constant list size. Our results in this note are as follows:- We provide a construction of subspace evasive sets in ${\mathbb F}^n$ of size $|{\mathbb F}|^{(1-\epsilon)n}$ that intersect any $k$-dimensional affine subspace of ${\mathbb F}^n$ in at most $(2/\epsilon)^k$ points. This slightly improves a recent construction of Dvir and Lovett (STOC 2012) in terms of the intersection size, who constructed similar sets, but with a bound of $(k/\epsilon)^k$ on the size of the intersection. Besides having a smaller intersection, our construction is more elementary. The construction is explicit when $k$ and $\epsilon$ are constants. This is sufficient in order to explicitly construct the aforementioned list-decodable codes. On the other hand, the construction of Dvir and Lovett is explicit in a stronger sense, and relies on solving systems of polynomial equations, while our construction relies on the method of conditional expectation.
- We use Kövári-Sós-Turán Theorem to show that for a certain range of parameters the subspace evasive sets obtained using the probabilistic method are optimal (up to a multiplicative constant factor).

**Simpler Exact Leader Election via Quantum Reduction**by Hirotada Kobayashi, Keiji Matsumoto, and Seiichiro Tani

December 16, 2014

The anonymous network model was introduced by Angluin in [STOC '80, pages 82-93] to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties. In this model, all parties with the same number of communication links are identical. When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party. It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication. This contrasts sharply with the situation in the quantum setting: that exactly solve the problem on anonymous*quantum*networks, where quantum communication and computation can be performed [TOCT, vol.4, no.1, article 1]. The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty. This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election. The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.

Volume 2013 Abstracts

Volume 2014 Published articles

Janos Simon