Search

A spin system is a general framework in which the vertices of a graph are assigned spins from a finite set. The local interactions between neighbouring spins give rise to a global weight, which describes the probability that the system is in the given configuration. Spin systems provide a framework for sampling and counting problems in computer science, graph homomorphism problems in combinatorics, and phase transition phenomena in statistical physics. Two natural computational problems associated to a spin system are counting (computing the aggregate weight of all spin configurations) and sampling (constructing a random spin configuration with probability proportional to its weight). In general, the problem of exact counting is computationally hard, and our attention therefore turns towards approximate counting, and the closely related problem of approximate sampling. In computer science, approximate counting and sampling for spin systems, such as the hard-core model on independent sets or the Potts model on colourings, are well-studied problems. In recent years, on bounded-degree graph classes, an intimate connection has been established between the computational complexity of approximate sampling and counting, and the the existence of phase transitions in corresponding statistical physics models. Roughly speaking, there is a phase transition between a 'high-temperature' regime and a 'low temperature' regime. In the hightemperature regime, interactions between spins are weak and there is disorder in the model. Conversely, in the low temperature regime, interactions between spins are strong and the model is highly ordered - a typical configuration corresponds to one of some number of ground states, which limit the way that spins are assigned. This behaviour is reflected by the algorithmic properties of these models. At high-temperatures, there exists a variety of algorithmic techniques for approximate counting and sampling - examples include the Markov chain Monte Carlo (MCMC) method and correlation decay. At low temperatures, these approaches no longer succeed. Indeed, for many spin systems on many interesting classes of graphs, the problems of approximate counting and sampling are provably intractable. Recent research has sought to understand the algorithmic behaviour of spin systems such as the hard-core and Potts models on graphs such as the integer lattice and the random regular graph, the latter of which can be seen as an 'average case' instance of a regular graph. A detailed algorithmic and probabilistic understanding of these models has been developed, and has resulted in efficient low temperature algorithms. This is in contrast to the case of arbitrary bounded-degree graphs, where efficient algorithms can usually only be achieved in the high-temperature regime. These approaches typically use the truncated Taylor series approach of Barvinok to approximate the log partition function of a certain convergent series expansion. As such, they rely on tools from the complex analysis literature, and typically have running times of the form n O(log ∆) , where ∆ is the maximum degree of the input graph. The work in this thesis can be seen as part of this same program - we develop efficient algorithmic approaches for approximate counting and sampling in low temperature spin systems, in a variety of different settings. We present a Markov chain based approach to approximate counting and sampling from spin systems such as the hard-core and Potts models. Using combinatorial and probabilistic techniques, we prove fast running times for these algorithms. Our results apply to classes of graphs such as the integer lattice, the random regular graph, and bounded-degree expanders, and they apply in a similar range of parameters to existing results. We also generalise these techniques to any spin system in which the interactions between spins are sufficiently strong, and to classes of random graphs of possibly unbounded degree.

The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists under the strict constraints, the task is to find a solution under the weak constraints. Austrin, Guruswami, and Hastad [SICOMP'17] showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of PCSPs on arbitrary finite domains. The hardness side is proved using the algebraic approach via a new general NP-hardness criterion on polymorphisms, which is based on a gap version of the Layered Label Cover problem. We show that previously used criteria are insufficient, and so this problem gives an interesting benchmark of algebraic techniques for proving hardness of approximation in problems such as PCSPs. Next we turn to non-symmetric PCSPs. While there now exist several dichotomy results for fragments of PCSPs, they all consider PCSPs that are symmetric in some way. 1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric CSPs. While both problems are NP-hard, Brakensiek and Guruswami showed [SICOMP'21] that given a satisfiable instance of 1-in-3-SAT, one can efficiently find a solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. In other words, the PCSP template (1-in-3, NAE) is tractable. We study PCSP templates obtained from the Boolean template (t-in-k, NAE) by either adding tuples to t-in-k or removing tuples from NAE. For the former, we obtain an "algorithmic dichotomy" and classify all templates as either tractable or not solvable by one of the strongest known algorithms for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek et al. [SICOMP'20]. For the latter, we classify all templates as either tractable or NP-hard. Finally, we investigate problems of the form PCSP(1-in-3, B) for B over an arbitrary finite domain. Barto, Battistelli, and Berg [STACS'21] almost completely classified such templates over domain size three, and suggested that over arbitrary domains, (1-in-3, NAE) and (1-in-3, C3) might be the only tractable templates, where C3 is a relation representing a 3-cycle. Through a connection to number theory, we exhibit an infinite family of tractable templates, of which (1-in-3, NAE) and (1-in-3, C3) are the simplest members. We conjecture that this family contains all tractable cases of PCSP(1-in-3, B), and we prove NP-hardness or non-solvability by BLP+AIP for certain PCSPs outside the family.

Shannon's theory of information laid the groundwork for the rapid developments in information and communications technologies over the last century. Yet, it assumed that information carriers were described by the laws of classical physics, whilst at the most fundamental level, nature obeys the laws of quantum physics. Quantum Shannon theory, which describes information carriers as quantum states, has led to a new era of possibilities, such as perfectly secure cryptography without pre-established keys. Yet, there is a sense in which this transition from classical to quantum is incomplete. Traditionally, quantum Shannon theory has focused on scenarios where the internal states of information carriers are quantum, whilst their trajectories in spacetime have still been assumed to be classical. This work presents a second level of quantisation where both the information itself and its propagation in spacetime are treated in a quantum fashion. The second-quantised Shannon theory describes the possibility of a single particle being simultaneously transmitted through multiple communication channels in a quantum superposition. The framework is developed using the tools of higher-order transformations and quantum resource theories, formally quantifying the resources required for communication between a sender and receiver in this setting. The advantages of the second-quantised theory are illustrated in a series of examples, showcasing various counterintuitive phenomena that occur when information is simultaneously transmitted through multiple communication channels. In particular, when a single particle travels in a quantum superposition through two alternative transmission lines, the noisy processes in the two lines can destructively interfere, leading to a cleaner communication channel overall. Various different scenarios are encompassed in the framework, including transmission through a superposition of both independent and correlated channels, as well as through large-scale communication networks. This work concludes with a study of the robustness of these protocols to errors and a discussion of recent experimental demonstrations of their associated communication advantages.

While the celebrated theory of NP-completeness has been very successful in explaining the intractability of many interesting problems, there still remain many natural and seemingly hard problems that are not known to be NP-hard. Several of these problems lie in the class of total NP search problems (TFNP), namely the class of NP search problems that always have a solution. Importantly, these problems cannot be NP-hard unless NP = co-NP. Notable examples of TFNP problems include FACTORING (given a natural number, compute its prime factorisation) and NASH (given a game, compute a mixed Nash equilibrium). In order to shed light on the complexity of these problems, researchers have attempted to classify them in various subclasses of TFNP such as PPAD, PPA, PPP, PLS, and CLS. A celebrated result in this line of research is the PPAD-completeness of NASH, yielding strong evidence that the problem is not polynomial-time solvable. In this thesis we provide new structural results for TFNP subclasses and show how they can be used to classify natural problems arising from application areas such as game theory and optimisation. In the first part of this work, we construct more powerful tools for proving membership in PPAD, as well as PPAD-hardness. We directly apply these tools to show that the Hairy Ball theorem from topology ("you can't comb a hairy ball flat without creating a cowlick"), as well as the equilibrium computation problem in First Price Auctions with subjective priors, are both PPAD-complete. In the second part of this thesis, we present our main result: the collapse CLS = PPAD ∩ PLS. We prove this surprising collapse by exhibiting the first non-artificial PPAD ∩ PLS-complete problem - a problem arising naturally from the famous gradient descent algorithm. Our result puts PPAD ∩ PLS on the map as a TFNP subclass that captures the complexity of natural problems. In the third and final part, we provide various structural results for the classes PPA-k (corresponding to arguments modulo k), including the first topological characterisations of these classes. As a direct application, we prove that NECKLACE-SPLITTING with k thieves - a notorious problem in combinatorics and fair division - lies in PPA-k under Turing reductions.

This thesis focuses on problems which themselves encode questions about circuits or algorithms, also called meta-computational problems. The thesis is centered on meta-computational problems like C-MCSP (minimum circuit size problem), C-Learnability and C-Satisfiability, for some circuit class C. We study mathematical questions pertaining to such problems, and their deep connections to the theory of lower bounds, which is a general theme that has attracted a lot of interest in recent years among complexity theorists. We first study non-uniform lower bounds for MCSP (and its variants) motivated by its importance for the theory of Hardness Magnification. Thisphenomenon reduces major complexity separations (such as NP is not in NC^1) to proving "barely" non-trivial lower bounds for natural problems like MCSP against weak circuit classes. In most interesting cases, we already have such required lower bounds, but for a different, seemingly easier problem. Firstly, we establish that instantiations of magnification for certain variants of MCSP provably refute the existence of natural proofs against P/poly, which indicates that the natural proofs barrier by Razborov-Rudich may not be relevant to this approach. This is done by establishing a connection from hardness magnification to hardness of efficiently learning polynomial-sized circuits. Next, we investigate the future prospects of proving new lower bounds using magnification. We identify a new source of difficulty called the locality barrier, when trying to adapt existing lower bound techniques to prove strong separations via magnification. We show that this barrier applies to many current instantiations of hardness magnification, that involve a wide range of restricted computational models. Next we consider learnability, and initiate a top-down study of hardness of learning circuit classes, i.e. we consider hardness of learning circuit classes more powerful than P/poly. Our goal is to understand the power and limitations of current complexity theoretic techniques in showing unconditional results for learning. We show unconditional hardness results for efficiently learning classes like BPE/poly, EXP/poly and PSPACE/poly on one hand, and on the other, show that it is implausible that one can extend these ideas to prove the NP-Hardness of learning classes like non-deterministic polynomial-sized circuits, i.e. NP/poly. Finally, we consider the algorithmic question of counting the number of satisfying assignments of an input AC^0[2]-circuit. We construct a deterministic #SAT-algorithm for AC^0[2] circuits of depth d and size 2^(O(n^(1/d))), which beats brute-force running time non-trivially. The algorithm is designed using the Razborov-Smolensky polynomial method, whose original motivation was to prove AC^0[2] lower bounds. We then show a lower bound for E^NP against AC^0[2]-circuits of size 2^(Ω(n^(1/d+1))), which was the best known lower bound against this class until very recently.

Mathematical logic and theoretical computer science are the mathematical studies of logic and computation, respectively, which largely correspond to each other notably by the Curry-Howard isomorphism. However, logic and computation have been captured mainly syntactically, which may be criticized as conceptually unclear and mathematically cumbersome. For this point, the field of semantics has been developed, i.e., its main aim is to explain logic and computation by mathematical and in particular syntax-independent concepts. However, logic and computation have not yet been completely captured semantically, where a main obstacle lies in the point that proofs and programs are central in these fields, and they are dynamic, intensional concepts, but mainstream mathematics has been concerned mainly with static, extensional objects such as sets and functions, lacking in dynamic, intensional structures. Motivated by this foundational problem, the present thesis is written for the aim of establishing mathematically rigorous, syntax-independent, conceptually natural semantics of some central aspects of logic and computation, particularly their dynamics and intensionality, that have not been captured very well from a conceptual or mathematical viewpoint, for which our primary goal is to obtain a deeper understanding of logic and computation. Specifically, the thesis is concerned with concepts such as proof-normalization in logic (or reduction in computation), higher-order computability, and predicates in logic (or dependent types in computation). Our approach is based on mathematical structures developed in the field of game semantics for they are mathematically rigorous, syntax-independent, conceptually natural and exible enough to model various kinds of logic and computation in a systematic manner; also, they have a good potential to capture dynamics and intensionality of logic and computation. More concretely, we generalize, for each concept mentioned above, an existing variant of games to capture the concept, where each case is confirmed by a certain soundness or sometimes completeness theorem. Since each of the generalizations is orthogonal to one another, we may combine them into a single framework that provides a unified view on these developments. As technical achievements of the thesis, many of the generalizations give the first game-semantic interpretations of the corresponding concepts, for which we have introduced a number of novel mathematical structures and proved their properties. Also, conceptually, our games give dynamic, intensional semantics that explains various concepts and phenomena in a natural, intuitive yet mathematically precise manner, e.g., normalization of reduction, Π-, Σ- and Id-types as well as universes in Martin-Lof type theory, incompatibility of Σ-types and classical reasoning, and nonconstructivity of Univalence Axiom in homotopy type theory. Last but not least, since our mathematical structures capture logic and computation more completely, well beyond conventional game semantics, one of their implications would be the semantics-first-view: Logic and computation may be understood abstractly and syntax-independently as mathematics, viz., games, rather than as syntactic entities to be analyzed by various semantics, which is our intention behind the title of the thesis. In particular, our game-semantic approach enables an analytic study of logic and computation, as opposed to more standard synthetic ones such as categorical semantics, in the sense that it reduces the two concepts to the highly primitive notions of '(dialogical) arguments' between prover and refuter mathematicians, and '(computational) processes' between a computational agent and an environment, respectively, giving a deeper understanding of the very notion of logic and computation. The former can be seen particularly as a unity of proof theory and model theory: It gives a syntax-independent formulation of proofs that is also a computational description of models (by which we mean what formal languages refer to in a loose sense), namely strategies, where provability and validity of a formula simply coincide as the existence of a winning strategy on the corresponding game. By this unity, the central questions of soundness and completeness in logic just disappear. Furthermore, consistency of the logic which our games and strategies embody is immediate. These points demonstrate certain technical advantages (in addition to the conceptual naturality mentioned above) of our game-semantic approach to logic.