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.

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.

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.

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.

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:

1. 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.
2. 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}$).
3. 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.

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.

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.

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.

• 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).