Search

Nearly a decade ago, Azrieli and Shmaya introduced the class of λ-Lipschitz games in which every player's payoff function is λ-Lipschitz with respect to the actions of the other players. They showed via the probabilistic method that n-player Lipschitz games with m strategies per player have pure ε-approximate Nash equilibria, for ε ≥ λ√8nlog(2mn). They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop an efficient reduction from more general games to Lipschitz games. We use this reduction to study both the query and computational complexity of algorithms finding λ-approximate pure Nash equilibria of λ-Lipschitz games and related classes. We show a query lower bound exponential in nλ/ε against randomized algorithms finding ε-approximate pure Nash equilibria of n-player, λ-Lipschitz games. We additionally present the first PPAD-completeness result for finding pure Nash equilibria in a class of finite, non-Bayesian games (we show this for λ-Lipschitz polymatrix games for suitable pairs of values ε and λ) in which both the proof of PPAD-hardness and the proof of containment in PPAD require novel approaches (in fact, our approach implies containment in PPAD for any class of Lipschitz games in which payoffs from mixed-strategy profiles can be deterministically computed), and present a definition of "randomized PPAD". We define and subsequently analyze the class of "Multi-Lipschitz games", a generalization of Lipschitz games involving player-specific Lipschitz parameters in which the value of interest appears to be the average of the individual Lipschitz parameters. We discuss a dichotomy of the deterministic query complexity of finding ε-approximate Nash equilibria of general games and, subsequently, a query lower bound for λ-Lipschitz games in which any non-trivial value of ε requires exponentially-many queries to achieve. We examine which parts of this extend to the concepts of approximate correlated and coarse correlated equilibria, and in the process generalize the edge-isoperimetric inequalities to generalizations of the hypercube. Finally, we improve the block update algorithm presented by Goldberg and Marmolejo to break the potential boundary of a 0.75-approximation factor, presenting a randomized algorithm achieving a 0.7368-approximate Nash equilibrium making polynomially-many profile queries of an n-player 1/n-1-Lipschitz game with an unbounded number of actions.

In this thesis we consider base size and properties of the generating graph for finite groups. Let Ω = {1,...,n}, let Sₙ = Sym({1,...,n}) and let G ≤ Sₙ. A base for G is a sequence Λ = (ω₁, . . . , ωₖ) of points in Ω such that the pointwise stabilizer, G_{ω₁,...,ωₖ} , is the identity. The base size of G, denoted by b(G, Ω) or b(G), is the length of the shortest base. We say that Λ is an irredundant base if G > G_{ω₁} > G_{ω₁,ω₂} > ··· > G_{ω₁,ω₂,...,ωₖ} = 1. If no irredundant base is longer than Λ, then we say that Λ is a maximal irredundant base for G and denote its length by I(G). A group is called large base if it is either a product action or almost simple group, and its socle is one or more copies of the alternating group Aᵣ acting on k-sets. Let G be a primitive subgroup of Sₙ that is not large base. We prove that any irredundant base for G has size at most 5log₂n. This bound is best possible up to a small multiplicative constant and is the first logarithmic bound on the size of an irredundant base for such groups. We show that for any constant c, there are infinitely many primitive groups with maximal irredundant base size at least c times the minimal base size. As a corollary of the first result, the relational complexity of G, denoted RC(G) (see Definition 2.2.10), is at most 5log₂n + 1. In addition the maximal size of a minimal base and the height, denoted B(G) and H(G) (see Definitions 2.2.1 and 2.2.5), are both at most 5log₂n. Furthermore, we deduce that a base for G of size at most 5log₂n can be computed in polynomial time. The generating graph Γ(G) of a finite group G has vertex set the non-identity elements of G, with two elements connected exactly when they generate G. A coclique in a graph is an empty induced subgraph, so a coclique in Γ(G) is a subset of G such that no pair of elements generate G. A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of G form a coclique in Γ(G), but this coclique need not be maximal. Let G = Sₙ or Aₙ. We first determine when the intransitive maximal subgroups of G are maximal cocliques in Γ(G), and when they are not we find the unique maximal coclique in which they are contained. We then show that for sufficiently large n, the imprimitive maximal subgroups of G are all maximal cocliques in Γ(G). In addition, using the result on intransitive maximal subgroups we prove that a conjecture of Cameron, Lucchini, and Roney-Dougal holds for G under certain restrictions on n. Namely we prove that two elements of G have identical sets of neighbours in Γ(G) if and only if they belong to exactly the same maximal subgroups. Finally under another set of restrictions on n we then determine precisely which maximal subgroups are maximal cocliques in Γ(G).

The main goal of the thesis is to compare the distinguishing power of known combinatorial and algebraic graph invariants. Using the language of refinement operators (introduced in [32]) we derive known results relating the Weisfeiler-Leman algorithms and the invertible map tests. The former are a well known family of polynomial time algorithms parametrised by some natural number, each defining an equivalence on graphs which over-approximates graph isomorphism. The latter, introduced in [30], are parametrised by a natural number and a set of prime numbers. By generalising the concept of coherent algebras to an arbitrary field, we show that the invertible map tests can be viewed as a representation theoretic generalisation of the Weisfeiler-Leman algorithms. We also show that the equivalences defined by each invertible map test over the set of all prime numbers can be decided in polynomial time. This motivates an open question which could lead to interesting insights into the nature and computational complexity of graph isomorphism, as well as the descriptive complexity of finite graphs. We also use refinement operators to bound the expressive power of an infinitary logic with solvability quantifiers so as to study the relative power of the invertible map tests and known proof systems with algebraic rules; namely, bounded degree polynomial calculus, monomial calculus and Nullstellensatz calculus. These are well studied and have been used in the context of graph isomorphism in [14] and [39]. Our results generalise some of the work in the latter two papers and contribute to a deeper understanding of the apparently weaker Nullstellensatz calculus. More precisely, we show that the distinguishing power of Nullstellensatz calculus is essentially the same as that of monomial calculus. Furthermore, in the case of fields of characteristic 0, we show that Nullstellensatz calculus can simulate polynomial calculus in the case of the graph isomorphism problem; hence, combining this with a results by Grohe et al. [39], it follows that over characteristic 0, all three proof systems have similar distinguishing power to the Weisfeiler-Leman algorithms. Building on recent results by Brachter and Schweitzer [16] we look at the behaviour of the Weisfeiler-Leman algorithms on finite groups. Whilst hinting at potential conditions required to construct families of 2-nilpotent groups with high Weisfeiler-Leman dimension, we also show that the class of 2-nilpotent groups generated by trees has low Weisfeiler-Leman dimension. This naturally leads to the question as to whether classes of graphs with low Weisfeiler-Leman dimension generate classes of 2-nilpotent groups with low Weisfeiler-Leman dimension. Lastly, we show that there is a first-order definable reduction from group isomorphism to the isomorphism problem of Latin square graphs of Cayley tables of groups, and vice-versa. The existence of such a bi-interpretation implies that the Weisfeiler-Leman dimensions of finite groups and Latin square graphs of their Cayley tables have a similar asymptotic behaviour.

This thesis addresses computational questions arising in auctions with multiple goods available in multiple quantities, with a focus on establishing the tractability of auction mechanisms used in practice. It presents algorithms and hardness results for solving these auctions with the goal of maximising social welfare or revenue, and develops procedures to facilitate participating agents in expressing their preferences in the auction's bidding language. The 'strong-substitutes product-mix auction' was originally designed for the Bank of England by Paul Klemperer and continues to be run at least monthly. It introduces a novel bidding language, which allows agents to submit sealed-bid strong-substitutes preferences over an arbitrary number of goods available in multiple discrete units. We study this language geometrically and computationally, and establish connections to related bidding languages in the literature. In order to solve the strong-substitutes product-mix auction for social welfare, we develop the first efficient algorithms to find market-clearing prices and envy-free allocations of supply to participating bidders. The latter, in particular, requires solving a novel constrained matching problem. By contrast, we show that solving the auction for maximum revenue is APX-hard even in special cases, and present initial algorithms for this. Agents participating in this auction may have trouble expressing their preferences in the auction's bidding language when faced with a large number of goods or non-trivial demand. Instead, they may be able to answer queries about their value of a given bundle or their demand at given prices. We propose algorithms that learn a bidder's preferences, assuming access to a demand or valuation oracle. In a special case currently implemented by the Bank of England, we present a linear-time algorithm. We also show super-polynomial lower bounds on the query complexity in the general case. Our algorithms constitute the first approach for bidders to express non-trivial preferences in these languages, lowering the barrier for participation in the strong-substitutes product-mix auction. In the related 'arctic product-mix market', originally designed for the Icelandic government by Klemperer, buyers use a conceptually similar bidding language to express preferences across multiple divisible goods in conjunction with monetary budgets. In this setting we present a new coincidence of the solution concepts of competitive equilibrium and optimal revenue: market-clearing prices are unique, and these prices maximise not only social welfare but also revenue. We also provide an algorithm to identify these prices.

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.

Weighted voting games are a family of cooperative games, typically used to model voting situations where a number of agents (players) vote against or for a proposal. In such games, a proposal is accepted if an appropriately weighted sum of the votes exceeds a prespecified threshold. As the influence of a player over the voting outcome is not in general proportional to her assigned weight, various power indices have been proposed to measure each player's influence. The inverse power index problem is the problem of designing a weighted voting game that achieves a set of target influences according to a predefined power index. In the first part of this thesis, we study the computational complexity of the inverse problem when the power index belongs to the class of semivalues. We prove that the inverse problem is computationally intractable for a broad family of semivalues, including all regular semivalues. As a special case of our general result, we establish computational hardness of the inverse problem for the Banzhaf indices and the Shapley values, arguably the most popular power indices. In the second part, we design efficient approximation algorithms for the inverse semi-value problem. We develop a unified methodology that leads to computationally efficient algorithms that solve the inverse semivalue problem to any desired accuracy. We perform an extensive experimental evaluation of our algorithms on both synthetic and real inputs. Our experiments show that our algorithms are scalable and achieve higher accuracy compared to previous methods in the literature.

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.

Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different structures in G, thereby providing a framework that captures some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homomorphisms from a graph G to a triangle (three vertices pairwise connected by edges) correspond to proper 3-colourings of G. Furthermore, counting homomorphisms has close ties to statistical physics and the computation of partition functions. The complexity of computing and approximating homomorphism counts has therefore drawn a lot of attention over the last four decades. One of the most intriguing open problems in this line of research is determining, for every graph H, the complexity of approximately counting homomorphisms to H. In this thesis, we investigate the complexity of several closely related problems. Our main objective is to establish complete complexity classifications for large classes of graph homomorphism counting problems. The focus is on counting homomorphisms that satisfy additional properties related to surjectivity. Apart from (unrestricted) homomorphisms, we mainly concentrate on: - (vertex-)surjective homomorphisms, - compactions (vertex- and non-loop-edge-surjective homomorphisms), - retractions (also known as pre-colouring extensions or one-or-all list homomorphisms). The main contributions of this thesis are as follows: • We give a complete complexity dichotomy for exactly counting surjective homomorphisms. This dichotomy is the same classification that also holds for exactly counting homomorphisms, list homomorphisms and retractions. • We give a complete complexity dichotomy for exactly counting compactions. Notably, this dichotomy is different from the dichotomy for surjective homomorphisms and shows that exactly counting compactions is actually the "hardest" of the aforementioned exact counting problems. • We present a collection of approximation-preserving reductions between different homomorphism counting problems. This includes reductions that establish that approximately counting retractions is at least as hard as approximately counting surjective homomorphisms and also at least as hard as approximately counting compactions. In these reductions we use a Monte Carlo sampling algorithm and this appears to be the first time such an approach has been used to obtain approximation-preserving reductions. • We formalise a framework that can be used to generate #BIS-easiness results for approximately counting homomorphisms and retractions. This framework is based on reduction techniques introduced by Dyer, Goldberg, Greenhill and Jerrum. • We give a complete complexity trichotomy for approximately counting retractions to all square-free graphs. As a consequence, we present separations between the problem of approximately counting homomorphisms and that of approximately counting retractions, as well as between the problem of approximately counting retractions and that of approximately counting list homomorphisms. • We present new #BIS-easiness results for approximately counting homomorphisms and thereby settle the complexity of this problem for a rich class of graphs for which it was previously unresolved. • We give a complete complexity dichotomy for counting homomorphisms modulo 2 to all K₄-minor-free graphs. This confirms a conjecture by Faben and Jerrum for this class of graphs. We use novel global hardness gadgets, which can be used to subsume all previously known classifications. We strengthen the hardness results by ruling out subexponential-time algorithms, assuming rETH.

Knowledge graphs (KGs) represent information in a simple, interlinked format and are used in a variety of applications. Besides the standard reasoning tasks such as query answering, there has been an increasing need for new types of analysis. One such fundamental analysis task is entity comparison, i.e., determining what two entities have in common and how they are different. The importance of such a task can be seen in various applications such as product comparisons, and explainable recommender systems. This thesis studies the problem of entity comparison over knowledge graphs and presents a novel framework that models comparisons via similarity and difference queries. It is the first declarative comparison framework for linked data that treats both similarities and differences as first-class citizens. We first define the syntax and semantics of various types of comparison queries, motivating each type with examples and establishing important relations between different query types. Next, we study the complexity of the two fundamental decision problems over queries, namely the existence and verification problems, for basic comparison queries and for most specific similarity queries (MSSQs). We consider two underlying fragments of SPARQL, with and without arithmetic comparisons, and we show how they affect the complexity of the above problems, and which types of data they suit most. We then study practical aspects of computing the MSSQ. In particular, we establish an important uniqueness result for MSSQs and propose an efficient approximation algorithm. We implement an algorithm for computing acyclic similarity queries and evaluate its performance on large-scale KGs; our empirical results demonstrate the practical feasibility of our algorithm.

A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three pre-orders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting - and in most cases completely trivial - but the pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.

In program analysis, unknown properties for terms are typically represented symbolically as variables. Bound constraints on these variables can then specify multiple optimisation goals for computer programs and nd application in areas such as type theory, security, alias analysis and resource reasoning. Resolution of bound constraints is a problem steeped in graph theory; interdependencies between the variables is represented as a constraint graph. Additionally, constants are introduced into the system as concrete bounds over these variables and constants themselves are ordered over a lattice which is, once again, represented as a graph. Despite graph algorithms being central to bound constraint solving, most approaches to program optimisation that use bound constraint solving have treated their graph theoretic foundations as a black box. Little has been done to investigate the computational costs or design e cient graph algorithms for constraint resolution. Emerging examples of these lattices and bound constraint graphs, particularly from the domain of language-based security, are showing that these graphs and lattices are structurally diverse and could be arbitrarily large. Therefore, there is a pressing need to investigate the graph theoretic foundations of bound constraint solving. In this thesis, we investigate the computational costs of bound constraint solving from a graph theoretic perspective for Information Flow Analysis (IFA); IFA is a sub- eld of language-based security which veri es whether con dentiality and integrity of classified information is preserved as it is manipulated by a program. We present a novel framework based on graph decomposition for solving the (atomic) bound constraint problem for IFA. Our approach enables us to abstract away from connections between individual vertices to those between sets of vertices in both the constraint graph and an accompanying security lattice which defines ordering over constants. Thereby, we are able to achieve significant speedups compared to state-of-the-art graph algorithms applied to bound constraint solving. More importantly, our algorithms are highly adaptive in nature and seamlessly adapt to the structure of the constraint graph and the lattice. The computational costs of our approach is a function of the latent scope of decomposition in the constraint graph and the lattice; therefore, we enjoy the fastest runtime for every point in the structure-spectrum of these graphs and lattices. While the techniques in this dissertation are developed with IFA in mind, they can be extended to other application of the bound constraints problem, such as type inference and program analysis frameworks which use annotated type systems, where constants are ordered over a lattice.

The verification of real-time systems has gained much interest in the formal verification community during the past two decades. In this thesis, we investigate two real-time verification problems that benefit from the techniques normally used in untimed verification. The first part of this thesis is concerned with the monitoring of real-time specifications. We study the expressiveness of metric temporal logics over timed words, a problem that dates back to early 1990s. We show that the logic obtained by extending Metric Temporal Logic (MTL) with two families of new modalities is expressively complete for the Monadic First-Order Logic of Order and Metric (FO[<,+1]) in time-bounded settings. Furthermore, by allowing rational constants, expressive completeness also holds in the general (time-unbounded) setting. Finally, we incorporate several notions and techniques from LTL monitoring to obtain the first trace-length independent monitoring procedure for this logic. The second part of this thesis concerns a decision problem regarding UAVs: given a set of targets (each ascribed with a relative deadline) and flight times between each pair of targets, is there a way to coordinate a flock of k identical UAVs so that all targets are visited infinitely often and no target is ever left unvisited for a time longer than its relative deadline? We show that the problem is PSPACE-complete even in the single-UAV case, thereby corrects an erroneous claim from the literature. We then complement this result by proposing an efficient antichain-based approach where a delayed simulation is used to prune the state space. Experimental results clearly demonstrate the effectiveness of our approach.

In mathematical finance, the sensitivities of option prices to various market parameters, also known as the “Greeks”, reflect the exposure to different sources of risk. Computing these is essential to predict the impact of market moves on portfolios and to hedge them adequately. This is commonly done using Monte Carlo simulations. However, obtaining accurate estimates of the Greeks can be computationally costly. Multilevel Monte Carlo offers complexity improvements over standard Monte Carlo techniques. However the idea has never been used for the computation of Greeks. In this work we answer the following questions: can multilevel Monte Carlo be useful in this setting? If so, how can we construct efficient estimators? Finally, what computational savings can we expect from these new estimators? We develop multilevel Monte Carlo estimators for the Greeks of a range of options: European options with Lipschitz payoffs (e.g. call options), European options with discontinuous payoffs (e.g. digital options), Asian options, barrier options and lookback options. Special care is taken to construct efficient estimators for non-smooth and exotic payoffs. We obtain numerical results that demonstrate the computational benefits of our algorithms. We discuss the issues of convergence of pathwise sensitivities estimators. We show rigorously that the differentiation of common discretisation schemes for Ito processes does result in satisfactory estimators of the the exact solutions’ sensitivities. We also prove that pathwise sensitivities estimators can be used under some regularity conditions to compute the Greeks of options whose underlying asset’s price is modelled as an Ito process. We present several important results on the moments of the solutions of stochastic differential equations and their discretisations as well as the principles of the so-called “extreme path analysis”. We use these to develop a rigorous analysis of the complexity of the multilevel Monte Carlo Greeks estimators constructed earlier. The resulting complexity bounds appear to be sharp and prove that our multilevel algorithms are more efficient than those derived from standard Monte Carlo.

Query processing is a core task in probabilistic databases: Given a query and a database that encodes uncertainty in data by means of probability distributions, the problem is to compute possible query answers together with their respective probabilities of being correct. This thesis advances the state of the art in two aspects of query processing in probabilistic databases: complexity analysis and query evaluation techniques. A dichotomy is established for non-repeating, con- junctive relational algebra queries with negation that separates #P-hard queries from those with PTIME data complexity. A framework for computing proba- bilities of relational algebra queries is presented; the probability computation algorithm is based on decomposition methods and provides exact answers in the case of exhaustive decompositions, or anytime approximate answers with absolute or relative error guarantees in the case of partial decompositions. The framework is extended to queries with aggregation operators. An experimental evaluation of the proposed algorithms’ implementations within the SPROUT query engine complements the theoretical results. The SPROUT2 system uses this query engine to compute answers to queries on uncertain, tabular Web data.

Description Logics form a family of powerful ontology languages widely used by academics and industry experts to capture and intelligently manage knowledge about the world. A key advantage of Description Logics is their amenability to automated reasoning that enables the deduction of knowledge that has not been explicitly stated. However, in order to ensure decidability of automated reasoning algorithms, suitable restrictions are usually enforced on the shape of structures that are expressible using Description Logics. As a consequence, Description Logics fall short of expressive power when it comes to representing cyclic structures, which abound in life sciences and other disciplines. The objective of this thesis is to explore ontology languages that are better suited for the representation of structured objects. It is suggested that an alternative approach which relies on nonmonotonic existential rules can provide a promising candidate for modelling such domains. To this end, we have built a comprehensive theoretical and practical framework for the representation of structured entities along with a surface syntax designed to allow the creation of ontological descriptions in an intuitive way. Our formalism is based on nonmonotonic existential rules and exhibits a favourable balance between expressive power and computational as well as empirical tractability. In order to ensure decidability of reasoning, we introduce a number of acyclicity criteria that strictly generalise many of the existing ones. We also present a novel stratification condition that properly extends `classical' stratification and allows for capturing both definitional and conditional aspects of complex structures. The applicability of our formalism is supported by a prototypical implementation, which is based on an off-the-shelf answer set solver and is tested over a realistic knowledge base. Our experimental results demonstrate improvement of up to three orders of magnitude in comparison with previous evaluation efforts and also expose numerous modelling errors of a manually curated biochemical knowledge base. Overall, we believe that our work lays the practical and theoretical foundations of an ontology language that is well-suited for the representation of structured objects. From a modelling point of view, our approach could stimulate the adoption of a different and expressive reasoning paradigm for which robustly engineered mature reasoners are available; it could thus pave the way for the representation of a broader spectrum of knowledge. At the same time, our theoretical contributions reveal useful insights into logic-based knowledge representation and reasoning. Therefore, our results should be of value to ontology engineers and knowledge representation researchers alike.

The search for the closest lattice point arises in many communication problems, and is known to be NP-hard. The Maximum Likelihood (ML) Detector is the optimal detector which yields an optimal solution to this problem, but at the expense of high computational complexity. Existing near-optimal methods used to solve the problem are based on the Sphere Decoder (SD), which searches for lattice points confined in a hyper-sphere around the received point. The SD has emerged as a powerful means of finding the solution to the ML detection problem for MIMO systems. However the bottleneck lies in the determination of the initial radius. This thesis is concerned with the detection of transmitted wireless signals in Multiple-Input Multiple-Output (MIMO) digital communication systems as efficiently and effectively as possible. The main objective of this thesis is to design efficient ML detection algorithms for MIMO systems based on the depth-first search (DFS) algorithms whilst taking into account complexity and bit error rate performance requirements for advanced digital communication systems. The increased capacity and improved link reliability of MIMO systems without sacrificing bandwidth efficiency and transmit power will serve as the key motivation behind the study of MIMO detection schemes. The fundamental principles behind MIMO systems are explored in Chapter 2. A generic framework for linear and non-linear tree search based detection schemes is then presented Chapter 3. This paves way for different methods of improving the achievable performance-complexity trade-off for all SD-based detection algorithms. The suboptimal detection schemes, in particular the Minimum Mean Squared Error-Successive Interference Cancellation (MMSE-SIC), will also serve as pre-processing as well as comparison techniques whilst channel capacity approaching Low Density Parity Check (LDPC) codes will be employed to evaluate the performance of the proposed SD. Numerical and simulation results show that non-linear detection schemes yield better performance compared to linear detection schemes, however, at the expense of a slight increase in complexity. The first contribution in this thesis is the design of a near ML-achieving SD algorithm for MIMO digital communication systems that reduces the number of search operations within the sphere-constrained search space at reduced detection complexity in Chapter 4. In this design, the distance between the ML estimate and the received signal is used to control the lower and upper bound radii of the proposed SD to prevent NP-complete problems. The detection method is based on the DFS algorithm and the Successive Interference Cancellation (SIC). The SIC ensures that the effects of dominant signals are effectively removed. Simulation results presented in this thesis show that by employing pre-processing detection schemes, the complexity of the proposed SD can be significantly reduced, though at marginal performance penalty. The second contribution is the determination of the initial sphere radius in Chapter 5. The new initial radius proposed in this thesis is based on the variable parameter α which is commonly based on experience and is chosen to ensure that at least a lattice point exists inside the sphere with high probability. Using the variable parameter α, a new noise covariance matrix which incorporates the number of transmit antennas, the energy of the transmitted symbols and the channel matrix is defined. The new covariance matrix is then incorporated into the EMMSE model to generate an improved EMMSE estimate. The EMMSE radius is finally found by computing the distance between the sphere centre and the improved EMMSE estimate. This distance can be fine-tuned by varying the variable parameter α. The beauty of the proposed method is that it reduces the complexity of the preprocessing step of the EMMSE to that of the Zero-Forcing (ZF) detector without significant performance degradation of the SD, particularly at low Signal-to-Noise Ratios (SNR). More specifically, it will be shown through simulation results that using the EMMSE preprocessing step will substantially improve performance whenever the complexity of the tree search is fixed or upper bounded. The final contribution is the design of the LRAD-MMSE-SIC based SD detection scheme which introduces a trade-off between performance and increased computational complexity in Chapter 6. The Lenstra-Lenstra-Lovasz (LLL) algorithm will be utilised to orthogonalise the channel matrix H to a new near orthogonal channel matrix H ̅.The increased computational complexity introduced by the LLL algorithm will be significantly decreased by employing sorted QR decomposition of the transformed channel H ̅ into a unitary matrix and an upper triangular matrix which retains the property of the channel matrix. The SIC algorithm will ensure that the interference due to dominant signals will be minimised while the LDPC will effectively stop the propagation of errors within the entire system. Through simulations, it will be demonstrated that the proposed detector still approaches the ML performance while requiring much lower complexity compared to the conventional SD.

Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects. Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach. The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.

In this thesis we consider two sets of combinatorial structures defined on an Eulerian graph: the Eulerian orientations and Euler tours. We are interested in the computational problems of counting (computing the number of elements in the set) and sampling (generating a random element of the set). Specifically, we are interested in the question of when there exists an efficient algorithm for counting or sampling the elements of either set. The Eulerian orientations of a number of classes of planar lattices are of practical significance as they correspond to configurations of certain models studied in statistical physics. In 1992 Mihail and Winkler showed that counting Eulerian orientations of a general Eulerian graph is #P-complete and demonstrated that the problem of sampling an Eulerian orientation can be reduced to the tractable problem of sampling a perfect matching of a bipartite graph. We present a proof that this problem remains #Pcomplete when the input is restricted to being a planar graph, and analyse a natural algorithm for generating random Eulerian orientations of one of the afore-mentioned planar lattices. Moreover, we make some progress towards classifying the range of planar graphs on which this algorithm is rapidly mixing by exhibiting an infinite class of planar graphs for which the algorithm will always take an exponential amount of time to converge. The problem of counting the Euler tours of undirected graphs has proven to be less amenable to analysis than that of Eulerian orientations. Although it has been known for many years that the number of Euler tours of any directed graph can be computed in polynomial time, until recently very little was known about the complexity of counting Euler tours of an undirected graph. Brightwell and Winkler showed that this problem is #P-complete in 2005 and, apart from a few very simple examples, e.g., series-parellel graphs, there are no known tractable cases, nor are there any good reasons to believe the problem to be intractable. Moreover, despite several unsuccessful attempts, there has been no progress made on the question of approximability. Indeed, this problem was considered to be one of the more difficult open problems in approximate counting since long before the complexity of exact counting was resolved. By considering a randomised input model, we are able to show that a very simple algorithm can sample or approximately count the Euler tours of almost every d-in/d-out directed graph in expected polynomial time. Then, we present some partial results towards showing that this algorithm can be used to sample or approximately count the Euler tours of almost every 2d-regular graph in expected polynomial time. We also provide some empirical evidence to support the unproven conjecture required to obtain this result. As a sideresult of this work, we obtain an asymptotic characterisation of the distribution of the number of Eulerian orientations of a random 2d-regular graph.

The purpose of this research work is to demonstrate the feasibility of creating a quick response decision platform for middle management in industry. It utilises the strengths of current, but more importantly creates a leap forward in the theory and practice of Supervisory and Data Acquisition (SCADA) systems and Discrete Event Simulation and Modelling (DESM). The proposed research platform uses real-time data and creates an automatic platform for real-time and predictive system analysis, giving current and ahead of time information on the performance of the system in an efficient manner. Data acquisition as the backend connection of data integration system to the shop floor faces both hardware and software challenges for coping with large scale real-time data collection. Limited scope of SCADA systems does not make them suitable candidates for this. Cost effectiveness, complexity, and efficiency-orientation of proprietary solutions leave space for more challenge. A Flexible Data Input Layer Architecture (FDILA) is proposed to address generic data integration platform so a multitude of data sources can be connected to the data processing unit. The efficiency of the proposed integration architecture lies in decentralising and distributing services between different layers. A novel Sensitivity Analysis (SA) method called EvenTracker is proposed as an effective tool to measure the importance and priority of inputs to the system. The EvenTracker method is introduced to deal with the complexity systems in real-time. The approach takes advantage of event-based definition of data involved in process flow. The underpinning logic behind EvenTracker SA method is capturing the cause-effect relationships between triggers (input variables) and events (output variables) at a specified period of time determined by an expert. The approach does not require estimating data distribution of any kind. Neither the performance model requires execution beyond the real-time. The proposed EvenTracker sensitivity analysis method has the lowest computational complexity compared with other popular sensitivity analysis methods. For proof of concept, a three tier data integration system was designed and developed by using National Instruments’ LabVIEW programming language, Rockwell Automation’s Arena simulation and modelling software, and OPC data communication software. A laboratory-based conveyor system with 29 sensors was installed to simulate a typical shop floor production line. In addition, EvenTracker SA method has been implemented on the data extracted from 28 sensors of one manufacturing line in a real factory. The experiment has resulted 14% of the input variables to be unimportant for evaluation of model outputs. The method proved a time efficiency gain of 52% on the analysis of filtered system when unimportant input variables were not sampled anymore. The EvenTracker SA method compared to Entropy-based SA technique, as the only other method that can be used for real-time purposes, is quicker, more accurate and less computationally burdensome. Additionally, theoretic estimation of computational complexity of SA methods based on both structural complexity and energy-time analysis resulted in favour of the efficiency of the proposed EvenTracker SA method. Both laboratory and factory-based experiments demonstrated flexibility and efficiency of the proposed solution.

The field of computational complexity theory--which chiefly aims to quantify the difficulty encountered when performing calculations--is, in the case of conventional computers, correctly practised and well understood (some important and fundamental open questions notwithstanding); however, such understanding is, we argue, lacking when unconventional paradigms are considered. As an illustration, we present here an analogue computer that performs the task of natural-number factorization using only polynomial time and space; the system's true, exponential complexity, which arises from requirements concerning precision, is overlooked by a traditional, `time-and-space' approach to complexity theory. Hence, we formulate the thesis that unconventional computers warrant unconventional complexity analysis; the crucial omission from traditional analysis, we suggest, is consideration of relevant resources, these being not only time and space, but also precision, energy, etc. In the presence of this multitude of resources, however, the task of comparing computers' efficiency (formerly a case merely of comparing time complexity) becomes difficult. We resolve this by introducing a notion of overall complexity, though this transpires to be incompatible with an unrestricted formulation of resource; accordingly, we define normality of resource, and stipulate that considered resources be normal, so as to rectify certain undesirable complexity behaviour. Our concept of overall complexity induces corresponding complexity classes, and we prove theorems concerning, for example, the inclusions therebetween. Our notions of resource, overall complexity, normality, etc. form a model-independent framework of computational complexity theory, which allows: insightful complexity analysis of unconventional computers; comparison of large, model-heterogeneous sets of computers, and correspondingly improved bounds upon the complexity of problems; assessment of novel, unconventional systems against existing, Turing-machine benchmarks; increased confidence in the difficulty of problems; etc. We apply notions of the framework to existing disputes in the literature, and consider in the context of the framework various fundamental questions concerning the nature of computation.

While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c^k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n^k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.

This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average size of a forest in a graph. We generalise this result to any simplicial complex. We answer a question posed by Kleinschmidt and Onn (1995) by showing that the language of partitionable simplicial complexes is in NP. We prove the following result concerning the complexity of the Tutte polynomial: Theorem 1. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers x and y, and evaluate the Tutte polynomial, T(G;x,y). The rank generating function S of a graphic 2-polymatroid was introduced by Oxley and Whittle (1993). It has many similarities to the Tutte polynomial and we prove the following results. Theorem 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial time algorithm. Theorem 3. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers u and v, and evaluate S(G;u,v). We consider a class of graphs $S$, which are those graphs which are obtainable from a graph with no edges using the unsigned version of Reidemeister moves. We examine the relationship between this class and other similarly defined classes such as the delta-wye graphs. There remain many open questions such as whether S contains every graph. However we have an invariant of the moves, based on the Tutte polynomial, which allows us to determine from which graph with no edges, if any, a particular graph can be obtained. Finally we consider a new polynomial on weighted graphs which is motivated by the study of weight systems on chord diagrams. We give three states model and a recipe theorem. An unweighted version of this polynomial is shown to contain as specialisations, a wide range of graph invariants, such as the Tutte polynomial, the polymatroid polynomial of Oxley and Whittle (1993) and the symmetric function generalisation of the chromatic polynomial introduced by Stanley (1995). We close with a discussion of complexity issues proving hardness results for very restricted classes of graphs.

Problem: Complex systems are composed of many interdependent subsystems with a level of complexity that exceeds the ability of a single designer. One way to address this problem is to partition the complex design problem into smaller, more manageable design tasks that can be handled by multiple design teams. Partitioning-based design methods are decision support tools that provide mathematical foundations, and computational methods to create such design processes. Managing the interdependency among these subsystems is crucial and a successful design process should meet the requirements of the whole system which needs coordinating the solutions for all the partitions after all. Approach: Partitioning and coordination should be performed to break down the system into subproblems, solve them and put these solutions together to come up with the ultimate system design. These two tasks of partitioning-coordinating are computationally demanding. Most of the proposed approaches are either computationally very expensive or applicable to only a narrow class of problems. These approaches also use exact methods and eliminate the uncertainty. To manage the computational complexity and uncertainty, we approximate each subproblem after partitioning the whole system. In engineering design, one way to approximate the reality is using surrogate models (SM) to replace the functions which are computationally expensive to solve. This task also is added to the proposed computational framework. Also, to automate the whole process, creating a knowledge-based reusable template for each of these three steps is required. Therefore, in this dissertation, we first partition/decompose the complex system, then, we approximate the subproblem of each partition. Afterwards, we apply coordination methods to guide the solutions of the partitions toward the ultimate integrated system design. Validation: The partitioning-approximation-coordination design approach is validated using the validation square approach that consists of theoretical and empirical validation. Empirical validation of the design architecture is carried out using two industry-driven problems namely the a hot rod rolling problem’, ‘a dam network design problem’, ‘a crime prediction problem’ and ‘a green supply chain design problem’. Specific sub-problems are formulated within these problem domains to address various research questions identified in this dissertation. Contributions: The contributions from the dissertation are categorized into new knowledge in five research domains: • Creating an approach to building an ensemble of surrogate models when the data is limited – when the data is limited, replacing computationally expensive simulations with accurate, low-dimensional, and rapid surrogates is very important but non-trivial. Therefore, a cross-validation-based ensemble modeling approach is proposed. • Using temporal and spatial analysis to manage the uncertainties - when the data is time-based (for example, in meteorological data analysis) and when we are dealing with geographical data (for example, in geographical information systems data analysis), instead of feature-based data analysis time series analysis and spatial statistics are required, respectively. Therefore, when the simulations are for time and space-based data, surrogate models need to be time and space-based. In surrogate modeling, there is a gap in time and space-based models which we address in this dissertation. We created, applied and evaluated the effectiveness of these models for a dam network planning and a crime prediction problem. • Removing assumptions regarding the demand distributions in green supply chain networks – in the existent literature for supply chain network design, there are always assumptions about the distribution of the demand. We remove this assumption in the partition-approximate-compose of the green supply chain design problem. • Creating new knowledge by proposing a coordination approach for a partitioned and approximated network design. A green supply chain under online (pull economy) and in-person (push economy) shopping channels is designed to demonstrate the utility of the proposed approach.

Since Valiant’s establishment of matrix rigidity to analyse circuit complexity, various contributions to the bounds of matrix rigidity of special candidates has bloomed. In this thesis, we cover the following topics: existing explicit and semi-explicit rigidity lower bounds for various families of matrices, Paturi-Pudlák dimensions, rigid sets, connections between data structure lower bounds and rigidity lower bounds and non-rigidity results.

Collective decision making arises in many real life situations, such as elections, matching applicants to job openings, and partitioning students into working groups. Over the past three decades, computer scientists have used techniques from the design and analysis of algorithms and complexity theory to develop social choice theory from a computational perspective, leading to the new research area of computational social choice theory. Broadly speaking, this dissertation makes two kinds of contributions to this new research area. First, we provide new algorithms and hardness results for two settings. In our first setting, we revisit the classical housing markets model in which we seek to compute a suitable reallocation of n houses to n agents, each of whom initially owns a particular house and has strict preferences over the set of n houses. In the variants of this model that we study, graph-based restrictions are imposed on the exchange of houses. More specifically, we consider two cases. In the first case, we are given a graph where the vertex set corresponds to the set of agents, and we assume that two agents can only swap houses if they are adjacent in the graph and the swap is Pareto-improving; thus, in this case, the locations of the agents remain fixed in the graph, while the houses can move around. The second case is similar except we assume that the locations of the houses remain fixed (i.e., each vertex now corresponds to a house) and the agents move around. In our second setting, we consider a variant of the classical coalition formation game, the fractional hedonic game. Such a game can be represented by a directed weighted graph where the set of vertices corresponds to the set of players, and where the weight of an edge (i,j) from player i to player j denotes the value that player i has for player j. Given a partitioning of the players into coalitions, the utility of player i is defined to be the average value that player i assigns to the members of their coalition. We assume that there is a limit on the number of coalitions that can be formed. In this setting, we study the problem of computing a social welfare maximizing partition and the problem of computing a Nash stable partition. We study these two problems for a variety of different graph classes. Second, we design mechanisms without money for new games related to facility location and resource sharing. In the facility location game that we consider, a central planner plans to build a heterogeneous set of facilities (e.g., a school, a water treatment plant) and each agent reports which of these facilities they consider to be “obnoxious”. The location of each agent is assumed to be fixed, and the utility of an agent is based on the minimum distance of the agent to an obnoxious facility. The goal is to design strategyproof mechanisms that maximize either the sum of the agent utilities or the minimum utility of any agent. In the resource sharing game that we consider, agents pool their computational resources in order to better accommodate fluctuations in individual demand over a sequence of rounds, and the agents specify their demand for each round at the outset. We present a group-strategyproof and non-wasteful mechanism that guarantees each agent at least half of the utility they could achieve without sharing their resources.

A major open problem in proof complexity is to prove superpolynomial lower bounds for AC0[p]-Frege proofs. This system is the analog of AC0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years ([Raz87, Smo87]), there are no significant lower bounds for AC0[p]-Frege. Significant and extensive degree lower bounds have been obtained for a variety of subsystems of AC0[p]- Frege, including Nullstellensatz ([BIK+94]), Polynomial Calculus ([CEI96]), and SOS ([GV01]). However to date there has been no progress on AC0[p]-Frege lower bounds.In the first part of this thesis, we study constant-depth extensions of the Polynomial Calculus [GH03]. We show that these extensions are much more powerful than was previously known. Our main result is that small depth (≤ 43) Polynomial Calculus (over a sufficiently large field) can polynomially effectively simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams, Sum-of-Squares (SOS), and Positivstellensatz Calculus (Dynamic SOS). Additionally, they can also quasi-polynomially effectively simulate AC0[q]-Frege for any prime q independent of the characteristic of the underlying field. They can also effectively simulate TC0-Frege if the depth is allowed to grow proportionally. Thus, proving strong lower bounds for constant-depth extensions of Polynomial Calculus would not only give lower bounds for AC0[p]-Frege, but also for systems as strong as TC0-Frege. In the second part of this thesis, we deal with the flip side of proving new lower bounds for these systems. In this direction, we extend the recent lower bounds of Sokolov [Sok20] for Polynomial Calculus over {±1} variables to show for every prime p > 0, every n > 0 and κ = O(log n) the existence of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(logn) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at most κ original variables requires size exp?Ω(n2/(κ22κ(M + nlog(n)))) .

The final Chapter concerns a problem of partitioning graphs subject to certain restrictions. We prove that several subproblems are NP-complete.

We present here work on matching problems, namely hedonic games, also known as coalition formation games. We introduce two classes of hedonic games, Super Altruistic Hedonic Games (SAHGs) and Anchored Team Formation Games (ATFGs), and investigate the computational complexity of finding optimal partitions of agents into coalitions, or finding - or determining the existence of - stable coalition structures. We introduce a new stability notion for hedonic games and examine its relation to core and Nash stability for several classes of hedonic games.

Abstract: In distributed computing models, where some helper nodes assist the master in a large-scale computation, a big challenge is when these helpers straggle. The straggling of even a single helper node can significantly increase the processing time. Therefore, coded distributed computing has been proposed as a solution in many recent studies. Unfortunately, in some scenarios, the decoding complexity at the master is so significant that it undermines the benefit of distributing the computation. To allow for distributed computing in these cases, we propose a multi-layer coding strategy that allows some helpers to assist with the decoding. In this thesis, we focus on two scenarios, (1) when an extra layer of helpers are introduced to help with the master's decoding, and (2) fitting a distributed coding scheme when the computation naturally requires multiple layers with shuffling (for example FFT). In both scenarios, we propose a fully-coded structure that tolerates straggling in each step. Moreover, using low-complexity codes such as Raptor codes to further reduce the master's decoding load is studied.

People often adopt improved behaviors, products, or ideas through the influence of friends. This is modeled by emph{cascades}. One way to spread such positive elements through society is to identify those most influential agents---those that cause the maximum spread, and initiate the spread by seeding them. However, this strategy has a key difficulty: finding these influential seed nodes. This is difficult even if both the network structure and the way the cascade spreads are known. In emph{the influence maximization problem}, a central planner is given a graph and a limited budget $k$, and he needs to pick $k$ seeds such that the expected total number of infected vertices in the graph at the end of the cascade is maximized. This problem plays a central role in viral marketing, outbreak detection, rumor controls, etc. This thesis focuses on computational complexity, approximability and algorithm/heuristic design aspects of the influence maximization problem, with both emph{submodular} and emph{nonsubmodular} diffusion models. The first part of the thesis studies submodular influence maximization mainly in the computational complexity and algorithm analysis aspects, which includes some breakthroughs in understanding the approximability of submodular influence maximization and the theoretical performance of the well-studied greedy algorithm. The second part of the thesis focuses on nonsubmodular influence maximization. New sociologically founded nonsubmodular diffusion models are proposed, and we show how the seeding strategy for nonsubmodular diffusion models is fundamentally different compared to submodular diffusion models.

In nature there are a variety of self-assembling systems occurring at varying scales which give rise to incredibly complex behaviors. Theoretical models of self-assembly allow us to gain insight into the fundamental nature of self-assembly independent of the specific physical implementation. In Winfree's abstract tile assembly model (aTAM), the atomic components are unit square "tiles" which have "glues" on their four sides. Beginning from a seed assembly, these tiles attach one at a time during the assembly process in an asynchronous and nondeterministic manner. We can gain valuable insights into the nature of self-assembly by comparing different models of self-assembly which use fundamentally different mechanisms for local interactions. A powerful notion which allows us to compare models of self-assembly is simulation. The first result of this thesis examines the role of non-determinism in simulation. It shows that the universal simulation of directed aTAM systems requires undirectedness. A tile assembly model is said to be directed if it always assembles the same final assembly. We distinguish between two types of aTAM systems: cooperative systems and non-cooperative systems. In cooperative aTAM systems, we are able to enforce that in order for a tile to attach to an assembly, the glues of a tile must match two or more glues of neighboring tiles. On the other hand, in non-cooperative aTAM systems, tiles are able to attach to an assembly provided that one of the tile's glues match an exposed glue on the assembly. It is well known that the cooperative aTAM is computationally universal, and it is conjectured that the non-cooperative aTAM is not computationally universal. For our second result, we show that if we allow tiles to be polygons with six or more sides, then the class of non-cooperative systems is capable of universal computation. On the other hand, we show that the class of systems consisting of polygons with six or less sides is not capable of computing using any of the currently known methods.

In this dissertation, we study two problems that have the theme of extracting information from lower dimensional samples. A number of recent works have studied algorithms for entrywise $\ell_p$-\emph{low rank approximation}, namely algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$), output a rank-$k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j} |A_{i,j} - B_{i,j}|^p$ when $p > 0$; and $\|A-B\|_0 = \sum_{i,j} [A_{i,j} \neq B_{i,j}]$ for $p=0$, where $\|A-B\|_0$ denotes the number of entries $(i,j)$ for which $A_{i,j} \neq B_{i,j}$.For $p = 1$, this is often considered more robust than the SVD, while for $p = 0$ this corresponds to minimizing the number of disagreements, or robust PCA. This problem is known to be NP-hard for $p \in \{0,1\}$, already for $k = 1$, and while there are polynomial time approximation algorithms, their approximation factor is at best $\poly(k)$. It was left open if there was a polynomial-time approximation scheme (PTAS) for $\ell_p$-approximation for any $p \geq 0$. We show the following:\begin{enumerate} \item On the algorithmic side, for $p \in (0,2)$, we use a technique called \emph{sketching} to give the first $n^{\poly(k/\eps)}$ time $(1+\eps)$-approximation algorithm. For $p = 0$, there are various problem formulations, a common one being the binary setting for which $A\in\{0,1\}^{n\times d}$ and $B = U \cdot V$, where $U\in\{0,1\}^{n \times k}$ and $V\in\{0,1\}^{k \times d}$. For this setting, we obtain an algorithm with time $n \cdot d^{\poly(k/\eps)}$. \item On the hardness front, for $p \in (1,2)$, we show under the Small Set Expansion Hypothesis and Exponential Time Hypothesis (ETH), there is no constant factor approximation algorithm running in time $2^{k^{\delta}}$ for a constant $\delta > 0$, showing an exponential dependence on $k$ is necessary. We also show for finite fields of constant size, under the ETH, that any fixed constant factor approximation algorithm requires $2^{k^{\delta}}$ time for a constant $\delta > 0$.\end{enumerate} \emph{Population recovery} is the problem of learning an unknown distribution over an unknown set of $n$-bit strings, given access to independent \emph{traces} from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the {bit-flip} noise channel and for the erasure noise channel. In this dissertation we initiate the study of population recovery under the \emph{deletion channel}, in which each bit $b$ is independently \emph{deleted} with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the \emph{trace reconstruction} problem, which is a challenging problem that has received much recent attention. In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value $\ell > 1$. As our main sample complexity upper bound, we show that for any population size $\ell = o(\log n / \log \log n)$, a population of $\ell$ strings from $\zo^n$ can be learned under deletion channel noise using $\smash{2^{n^{1/2 + o(1)}}}$ samples. On the lower bound side, we show that at least $n^{\Omega{(\ell)}}$ samples are required to perform population recovery under the deletion channel when the population size is $\ell$, for all $\ell \leq n^{1/2 - \epsilon}$.

At its core, cryptography relies on problems that are simple to construct but difficult to solve unless certain information (the “key”) is known. Many of these problems come from number theory and group theory. One method of obtaining groups from which to build cryptosystems is to define algebraic curves over finite fields and then derive a group structure from the set of points on those curves. This thesis serves as an exposition of Elliptic Curve Cryptography (ECC), preceded by a discussion of some basic cryptographic concepts and followed by a glance into one generalization of ECC: cryptosystems based on hyperelliptic curves.

Statistical inference on high-dimensional and noisy data is a central concern of modern computer science. Often, the main challenges are inherently computational: the problems are well understood from a purely statistical perspective, but key statistical primitives -- likelihood ratios, Bayes-optimal estimators, etc. -- are intractable to compute on large and high-dimensional data sets. We develop a unified approach to algorithm design for statistical inference based on the Sum of Squares method, a powerful tool for convex programming with low-degree polynomials, which generalizes linear programming and spectral algorithms. We use this approach to design algorithms for a range of high-dimensional statistical problems, improving on state-of-the-art provable guarantees in several well-studied settings: clustering data from high-dimensional mixture models, community detection in random graphs, and more. We also prove computational lower bounds for some statistical problems, including the long-studied planted clique problem. Our lower bounds provide new strong evidence for the existence of information-computation gaps -- that is, statistical problems which are solvable given infinite computational resources, but not by efficient algorithms. In particular, we prove new lower bounds against the powerful Sum of Squares hierarchy of semidefinite programs, via a new technique called "pseudocalibration". Because the Sum of Squares hierarchy has provable guarantees matching those of most known techniques in algorithm design for inference, our lower bounds strongly suggest that the problems we study are intractable for polynomial-time algorithms. At very least, improving existing algorithms for them would require a major breakthrough. We show that polynomial-size semidefinite programs from the Sum of Squares hierarchy cannot refute the existence of cliques of size much less than the square root of n in n-node random graphs. Additionally, we prove a lower bound for sparse principal component analysis (PCA), showing that subexponential-size Sum of Squares semidefinite programs are needed to improve on the provable guarantees of existing spectral algorithms for sparse PCA. Our approach to algorithms and lower bounds suggests a new method to chart the edge of algorithmic tractability for statistical inference. We propose a classification of Bayesian inference problems according to solvability by algorithms which compute only simple statistics of input data -- triangle counts of graphs, top eigenvalues of matrices, etc. Our classification accurately predicts suspected information-computation gaps for many well-studied problems, including planted clique, planted constraint satisfaction, community detection in stochastic block models, component analysis problems, and more. This type of classification is novel for inference problems, and represents the first approach to trace the information-computation gaps in of all these problems to the same underlying mathematical structure.

It was found, by studying black holes, that the compatibility of the theory of gravity and the laws of quantum mechanics demands that the universe must act like a hologram. That is, all the information inside a region of the universe should be encoded on a so-called holographic screen of one-lesser dimension. This is termed the holographic principle. In a generic spacetime, such as an expanding universe, holographic screens depend on the choice of an observer, which is consistent with the notion that the observer is part of the system in cosmology. In the first part of this dissertation, we study the observer-dependence of holographic screens. This will help us understand how the fundamental description of the universe depends on the choice of the observer. Furthermore, we study the dynamics of the holographic screens and their geometry in the first part of this dissertation.An example where the holographic principle is manifest is the AdS-CFT correspondence. This correspondence connects quantum information quantities, like entanglement and complexity, to geometric quantities, like area and volume, respectively. In the second and the third part of this dissertation, we use the AdS-CFT correspondence as a tool to calculate the entanglement entropy and the computational complexity of a quenched CFT state. Studying the time evolution of the entanglement entropy following a quantum quench teaches us how a CFT state thermalizes. On the other hand, studying the time evolution of the computational complexity allows us to check the validity of various recent conjectures involving black holes and complexity.

As the modern integrated circuit continues to grow in complexity, the design of very large-scale integrated (VLSI) circuits involves massive teams employing state-of-the-art computer-aided design (CAD) tools. An old, yet significant CAD problem for VLSI circuits is physical design automation. In this problem, one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface. The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there exist several models for the clustering problem. In particular, we consider the problem of disjoint clustering in combinatorial circuits for delay minimization (CN). The problem of clustering with replication for delay minimization has been well-studied and known to be solvable in polynomial time. However, replication can become expensive when it is unbounded. Consequently, CN is a problem worth investigating. In this dissertation, we establish the computational complexities of several variants of CN. We also present approximation and exact exponential algorithms for some variants of CN. In some cases, we even obtain an approximation factor of strictly less than two. Furthermore, our exact exponential algorithms beat brute force.

Elections are arguably the best way that a group of agents with preferences over a set of choices can reach a decision. This can include political domains, as well as multiagent systems in artificial-intelligence settings. It is well-known that every reasonable election system is manipulable, but determining whether such a manipulation exists may be computationally infeasible. We build on an exciting line of research that considers the complexity of election-attack problems, which include voters misrepresenting their preferences (manipulation) and attacks on the structure of the election itself (control). We must properly model such attacks and the preferences of the electorate to give us insight into the difficulty of election attacks in natural settings. This includes models for how the voters can state their preferences, their structure, and new models for the election attack itself. We study several different natural models on the structure of the voters. In the computational study of election attacks it is generally assumed that voters strictly rank all of the candidates from most to least preferred. We consider the very natural model where voters are able to cast votes with ties, and the model where they additionally have a single-peaked structure. Specifically, we explore how voters with varying amounts of ties and structure in their preferences affect the computational complexity of different election attacks and the complexity of determining whether a given electorate is single-peaked. For the representation of the voters, we consider how representing the voters succinctly affects the complexity of election attacks and discuss how approaches for the nonsuccinct case can be adapted. Control and manipulation are two of the most commonly studied election-attack problems. We introduce a model of electoral control in the setting where some of the voters act strategically (i.e., are manipulators), and consider both the case where the agent controlling the election and the manipulators share a goal, and the case where they have competing goals. The computational study of election-attack problems allows us to better understand how different election systems compare to one another, and it is important to study these problems for natural settings, as this thesis does.

This thesis is concerned with routing and scheduling patrol assets to provide coverage of a pre-defined set of patrol regions. Two patrol routing and scheduling problems are studied: the Patrol Boat Scheduling Problem with Complete Coverage (PBSPCC) and the Maximum Covering and Patrol Routing Problem (MCPRP). The PBSPCC utilizes a patrol boat fleet to provide complete coverage of a set of maritime patrol regions, ensuring that there is at least one boat on station in each patrol region at any given time. This requirement is complicated by the fact that the boats cannot maintain patrol duties indefinitely. Before a maximum operational time has expired, a boat must return to port for a mandatory resource replenishment break, which may be required for crew layover time or refuelling. The PBSPCC is addressed by considering the operational performance of the patrol boats, the network topology, and the duration of a resource replenishment break. An additional aspect to the problem is to find the minimum number of patrol boats which can meet the complete coverage requirement indefinitely. The MCPRP is concerned with routing a fleet of patrol cars to provide maximum coverage of a set of accident hotspots on a road network, where each hotspot is given by a geographical location and a time window. The patrol cars maintain active duty over a pre-defined shift, with each car beginning and ending its shift at a depot. The objective is to maximize the aggregate presence of the patrol cars within the time windows, without double-counting of the patrol effort. This problem has received recent attention in the literature with the application of linear and integer programming models. We present new modelling and algorithmic approaches to address the aforementioned patrol coverage problems. The approaches are underpinned by specially tailored network design principles, Dantzig-Wolfe column generation, branch-and-price heuristics and various problem reduction techniques. We introduce a number of benchmark test instances for both the PBSPCC and MCPRP on which various column generation acceleration strategies are compared and analysed. The results for the PBSPCC indicate that our techniques can exploit certain problem structures to achieve optimal and good quality cyclic schedules in reasonable timeframes. For the MCPRP, the results show that a branch-and-price approach can be used to solve large-scale problem instances that cannot be handled by extant techniques.

Computational complexity theory studies which computational problems can be solved with limited access to resources. The past fifty years have seen a focus on the relationship between intractable problems and efficient algorithms. However, the relationship between inherently sequential problems and highly parallel algorithms has not been as well studied. Are there efficient but inherently sequential problems that admit some relaxed form of highly parallel algorithm? In this dissertation, we develop the theory of structural complexity around this relationship for three common types of computational problems. Specifically, we show tradeoffs between time, nondeterminism, and parallelizability. By clearly defining the notions and complexity classes that capture our intuition for parallelizable and sequential problems, we create a comprehensive framework for rigorously proving parallelizability and non-parallelizability of computational problems. This framework provides the means to prove whether otherwise tractable problems can be effectively parallelized, a need highlighted by the current growth of multiprocessor systems. The views adopted by this dissertation—alternate approaches to solving sequential problems using approximation, limited nondeterminism, and parameterization—can be applied practically throughout computer science.

In my Ph.D. dissertation, I have studied problems arising in various aspects of preferences: preference modeling, preference learning, and preference reasoning, when preferences concern outcomes ranging over combinatorial domains. Preferences is a major research component in artificial intelligence (AI) and decision theory, and is closely related to the social choice theory considered by economists and political scientists. In my dissertation, I have exploited emerging connections between preferences in AI and social choice theory. Most of my research is on qualitative preference representations that extend and combine existing formalisms such as conditional preference nets, lexicographic preference trees, answer-set optimization programs, possibilistic logic, and conditional preference networks; on learning problems that aim at discovering qualitative preference models and predictive preference information from practical data; and on preference reasoning problems centered around qualitative preference optimization and aggregation methods. Applications of my research include recommender systems, decision support tools, multi-agent systems, and Internet trading and marketing platforms.

The Stable Marriage Problem (SMP) is concerned with the follow scenario: suppose we have two disjoint sets of agents—for example prospective students and colleges, medical residents and hospitals, or potential romantic partners—who wish to be matched into pairs. Each agent has preferences in the form of a ranking of her potential matches. How should we match agents based on their preferences?We say that a matching is "stable" if no unmatched pair of agents mutually prefer each other to their assigned partners. In their seminal work on the SMP, Gale and Shapley prove that a stable matching exists for any preferences. They further describe an efficient algorithm for finding a stable matching. In this dissertation, we consider the computational complexity of the SMP in the distributed setting, and the complexity of finding “almost stable” matchings. Highlights include (1) communication lower bounds for finding stable and almost stable matchings, (2) a distributed algorithm which finds an almost stable matching in poly-logarithmic time, and (3) hardness of approximation results for three dimensional analogues of the SMP.

After several decades of development, higher-order finite-element methods are now being considered for realistic and large scale Computational Fluid Dynamics (CFD) simulations. This necessitates further studies on utilization of mesh adaptation techniques in order to reach reliable solutions at minimal computation cost. In this study, adaptation capabilities have been developed within a Petrov-Galerkin (PG) finite-element method. The mesh modification mechanisms include h-, p-, and combined hp-adaptations which are performed in a non-conforming manner. The constrained approximation method has been utilized in order to retain the continuity of the solution space in presence of hanging nodes. Hierarchical basis functions have been employed to facilitate the implementation of the constrained approximation method. The adaptive methodology has been demonstrated on numerous cases using the Euler and Reynolds Average Navier-Stokes (RANS) equations, equipped with a modified Spalart-Allmaras (SA) turbulence model. Also, a PDE-based artificial viscosity has been added to the governing equations, to stabilize the solution in the vicinity of shock waves. For accurate representation of the geometric surfaces, high-order curved boundary meshes have been generated and the interior meshes have been deformed through the solution of a modified linear elasticity equation. A fully implicit linearization has been utilized within a Newton-type algorithm to advance each iteration or time-step, for steady-state or unsteady simulations, respectively. In order to navigate the adaptation process, adjoint-based and feature-based techniques have been employed in the steady-state and unsteady problems, respectively. It was shown that weak implementation of the boundary conditions and the use of a modified functional are required to obtain a smooth adjoint solution where Dirichlet Boundary conditions are imposed. Failure to utilize both results in a non-smooth adjoint solution. To accelerate the error reduction, an enhanced h-refinement has been used in the vicinity of singularity points. Several numerical results illustrate consistent accuracy improvement of the functional outputs and capability enhancements in resolving complex viscous flow features such as shock boundary layer interaction, flow separation, and vortex shedding.

In an age of exponentially increasing data availability, performing inference tasks by utilizing the available information in its entirety is not always an affordable option. In this context, the present thesis introduces different methods for rendering large-scale linear regression and tracking of dynamic processes affordable, by processing a reduced number of data. The proposed algorithms utilize interval censoring of observations, in order to judiciously discard those deemed to have relatively small contribution towards enhancing the estimation or tracking accuracy. For linear regression, two groups of first- and second-order iterative algorithms are proposed: the first one focuses on reducing data storage and transmission costs, while the second is tailored for reducing the overall problem complexity. Leveraging principles of stochastic approximation, the introduced methods entail simple, closed-form updates, provable convergence guarantees, and can afford online processing of the data. As far as the tracking of dynamical processes, two distinct methods are put forth for reducing the number of data involved per time step. The first method builds on preprocessing the data for dimensionality reduction using low-complexity random projections, while the second performs censoring for data-adaptive measurement selection. Simulations on real and synthetic data, compare the proposed methods with competing alternatives and corroborate their efficacy in terms of estimation accuracy over complexity reduction.

In the hedonic coalition formation game model Roles Based Hedonic Games (RBHG), agents view teams as compositions of available roles. An agent's utility for a partition is based upon which role she fulfills within the coalition and which additional roles are being fulfilled within the coalition. I consider optimization and stability problems for settings with variable power on the part of the central authority and on the part of the agents. I prove several of these problems to be NP-complete or coNP-complete. I introduce heuristic methods for approximating solutions for a variety of these hard problems. I validate heuristics on real-world data scraped from League of Legends games.

Complex processes whose evolution in time rests on the occurrence of a large and random number of intermittent events are the systems under study. The mean time distance between two consecutive events is infinite, thereby violating the ergodic condition and activating at the same time a stochastic central limit theorem that explains why the Mittag-Leffler function is a universal property of nature. The time evolution of these complex systems is properly generated by means of fractional differential equations, thus leading to the interpretation of fractional trajectories as the average over many random trajectories, each of which fits the stochastic central limit theorem and the condition for the Mittag-Leffler universality. Additionally, the effect of noise on the generation of the Mittag-Leffler function is discussed. Fluctuations of relatively weak intensity can conceal the asymptotic inverse power law behavior of the Mittag-Leffler function, providing a reason why stretched exponentials are frequently found in nature. These results afford a more unified picture of complexity resting on the Mittag-Leffler function and encompassing the standard inverse power law definition.

In this dissertation we consider two notions of the "complexity" of a natural number, one being addition chain length, the other known as "integer complexity". The integer complexity of n, denoted ||n||, is the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. It is known that n>=3log_3(n) for all n. We consider the difference delta(n):=||n||−3log_3(n), which we call the defect of n. We consider the set of all defects - the set D:={delta(n) : n>=1}. We show that, as a set of real numbers, D is well-ordered, with order type omega^omega; we also show the same for several variants of D. Moreover, we show that, for k>=1 a natural number, the intersection of D with [0, k) has order type omega^k. We also use the defect to prove stabilization results about ||n||. Specifically, for any n, there exists K=K(n) such that for k>=K, we have delta(3^k*n)=delta(3^K*n). We call K(n) the stabilization length of n. Finally, we provide a way of, given r>0, computing all numbers n with delta(n)=0 with k+l>0. In parallel to our results for integer complexity, we also consider addition chain length. An addition chain for n is a sequence (a_0,a_1,...,a_r) such that a_0=1, a_r=n, and, for any k with 1=1}. We show that D is also a well-ordered set with order type omega^omega. We also use the defect to prove stabilization results about l(n); specifically, for any n, there exists K'=K'(n) such that for k>=K', we have delta^l(2^k*n)=delta^l(2^K'*n).

Spin systems originated in statistical physics as tools for modeling phase transitions in magnets. However, they have since been used to model complex systems arising in several other fields of study (e.g., in Bayesian inference and in the theory of social networks), so that various computational problems associated with them have received much attention in the literature. A lot of progress in the study of these problems has relied upon ideas from statistical physics; one example of this interplay has been the discovery of tight connections between the computational complexity of these problems and the phenomenon of phase transitions that many spin systems exhibit. Conversely, algorithmic ideas have also helped in the study of the phase transition phenomenon.This thesis presents two lines of work that fit into this theme. The first considers the approximation of the partition function, a pivotal quantity associated with spin systems. Here, we obtain—in various settings—deterministic polynomial time algorithms for approximating the partition function in the so called uniqueness regime, and thus strengthen the algorithmic side of the tight correspondence between phase transitions and the computational complexity of the partition function.The second line of work is concerned with the complexity of exact computation of various natural mean observables of spin systems, e.g., the magnetization in the Ising model. We relate these questions to the location of the complex zeros of the partition function, which have been studied in statistical physics because of their connections to the existence of phase transitions, and have been the subject of various celebrated results (such as the Lee–Yang theorem and the Heilmann–Lieb theorem). By proving a novel extension of the Lee–Yang theorem, we show that the magnetization of the ferromagnetic Ising model is indeed as hard to compute as the partition function (i.e., #P–hard). We also obtain similar results for the monomer–dimer model.

This thesis aims to theoretically study a modern linear transceiver design strategy, namely interference alignment, in wireless networks. We consider an interference channel whereby each transmitter and receiver are equipped with multiple antennas. The basic problem is to design optimal linear transceivers (or beamformers) that can maximize the system throughput. The recent work [1] suggests that optimal beamformers should maximize the total degrees of freedom through the interference alignment equations. In this thesis, we first state the interference alignment equations and study the computational complexity of solving these equations. In particular, we prove that the problem of maximizing the total degrees of freedom for a given interference channel is NP-hard. Moreover, it is shown that even checking the achievability of a given tuple of degrees of freedom is NP-hard when each receiver is equipped with at least three antennas. Interestingly, the same problem becomes polynomial time solvable when each transmit/receive node is equipped with no more than two antennas.The second part of this thesis answers an open theoretical question about interference alignment on generic channels: What degrees of freedom tuples (d1, d2, ..., dK) are achievable through linear interference alignment for generic channels? We partially answer this question by establishing a general condition that must be satisfied by any degrees of freedom tuple (d1, d2, ..., dK) achievable through linear interference alignment. For a symmetric system with dk = d for all k, this condition implies that the total achievable DoF cannot grow linearly with K, and is in fact no more than K(M + N)/(K + 1), where M and N are the number of transmit and receive antennas, respectively. We also show that this bound is tight when the number of antennas at each transceiver is divisible by the number of data streams.