Call a semantics for a language with variables \emph{absolute} when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable $a$ is a copy of itself in the denotation. We give a trio of lattice-based, sets-based, and algebraic absolute semantics to first-order logic. Possibly open predicates are directly interpreted as lattice elements / sets / algebra elements, subject to suitable interpretations of the connectives and quantifiers. In particular, universal quantification $\Forall{a}\phi$ is interpreted using a new notion of \emph{`fresh-finite'} limit $\freshwedge{a}\model{\phi}$ and using a novel dual to substitution. The interest of this semantics is partly in the non-trivial and beautiful technical details, which also offer certain advantages over existing semantics---but also the fact that such semantics exist at all suggests a new way of looking at variables and the foundations of logic and computation, which may be well-suited to the demands of modern computer science.

#### 63:3 Invited Articles Foreword

Eva TardosWe construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t=t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n*polylog(t). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et-al (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

We show an exponential gap between communication complexity and information complexity, by giving an explicit example of a partial boolean function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman, our gap is the largest possible. By a result of Braverman and Rao, our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the $\LOCAL$ model (where the input graph and underlying distributed network are identical) and study the {\em randomized} complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes \begin{itemize} \item An MIS algorithm running in $O(\log^2\Delta + 2^{O(\sqrt{\log\log n})})$ time, where $\Delta$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll \Delta \ll 2^{\sqrt{\log n}}$, and comes close to the $\Omega(\log \Delta)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. \item A maximal matching algorithm running in $O(\log\Delta + \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $\Delta$ is {\em provably optimal}. \item A $(\Delta+1)$-coloring algorithm requiring $O(\log\Delta + 2^{O(\sqrt{\log\log n})})$ time, improving on an $O(\log\Delta + \sqrt{\log n})$-time algorithm of Schneider and Wattenhofer. \item A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. \end{itemize} Each of our algorithms is based on a simple, but powerful technique for reducing a {\em randomized} symmetry breaking task to a corresponding {\em deterministic} one on a $\poly(\log n)$-size graph.

Randomness is a vital resource for modern day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high quality random numbers generated securely. Here we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in the devices, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions for the protocol. In conjunct with a recent work by Chung, Shi and Wu, it also leads to robust unbounded expansion using just 2 multi-part devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Renyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements, and a method for simulating trusted measurements with untrusted devices.

#### Constant rate PCPs for CircuitSat with sublinear query complexity

Ben-Sasson, Eli ; Kaplan, Yohay ; Kopparty, Swastik ; Meir, Or ; Stichtenoth, HenningWe prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.

#### Analyzing Network Coding (Gossip) Made Easy

Haeupler, BernhardWe consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently simple circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one en- coder/decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors: We give the first construction of a polynomial-time encod- able/decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1 H(p). These are channels which add an arbitrary error vector e {0, 1}^N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List-decoding for polynomial-time channels: For every constant c > 0, we give a Monte Carlo construction of an code with optimal rate (arbitrarily close to 1 H(p)) that efficiently recovers a short list containing the correct message with high probability for channels describable by circuits of size at most N^c. We are not aware of any channel models considered in the information theory literature, other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list-decoding with an impossibility result showing that, in a large range of parameters (p > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate.

Let M = (E,I) be a matroid and let S={S_1, ... , S_t} be a family of subsets
of E of size p. A subfamily ~~ subset of S is q-representative for S if for
every set Y subset of E of size at most q, if there is a set X in S disjoint
from Y with X \cup Y in I, then there is a set ~~~~ disjoint from Y
with ~~

#### Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

Dughmi, Shaddin ; Roughgarden, Tim ; Yan, QiqiIn the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected $n$-vertex graph $G$, a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of demand pairs and an integer $c$. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by $c$. When the maximum allowed congestion is $c=1$, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an $O(\sqrt n)$-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the $\Omega(\sqrt n)$ lower bound on the integrality gap of this relaxation. We show an $O(poly\log k)$-approximation algorithm for EDPwC with congestion $c=2$, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of $\tilde{\Omega}\left((\log n)^{1/(c+1)}\right )$ for any constant congestion $c$. Prior to our work, the best approximation factor for EDPwC with congestion $2$ was $\tilde O(n^{3/7})$, and the best algorithm achieving a polylogarithmic approximation required congestion $14$.

#### Approximation Resistance from Pairwise Independent Subgroups

Chan, Siu OnLock-free concurrent algorithms guarantee that \emph{some} concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were \emph{wait-free}, guaranteeing that \emph{all} operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a \emph{stochastic scheduler}. Our analysis relates the individual performance of processes with the global performance of the system using \emph{Markov chain lifting} between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability $1$, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n. Our main result states that for n-player binary-action games and for constant µ, the query complexity of an µ-well-supported Nash equilibrium is exponential in n. As a consequences of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.