On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Quantum stochastic calculus associated with quadratic quantum noises

We first study a class of fundamental quantum stochastic processes induced by the generators of a six dimensional non-solvable Lie dagger-algebra consisting of all linear combinations of the generalized Gross Laplacian and its adjoint, annihilation operator, creation operator, conservation, and time, and then we study the quantum stochastic integrals associated with the class of fundamental quantum stochastic processes, and the quantum Ito formula is revisited. The existence and uniqueness of solution of a quantum stochastic differential equation is proved. The unitarity conditions of solutions of quantum stochastic differential equations associated with the fundamental processes are examined. The quantum stochastic calculus extends the Hudson-Parthasarathy quantum stochastic calculus. (C) 2016 AIP Publishing LLC.

Games with perceptions

We assume that 2 x 2 matrix games are publicly known and that players perceive a dichotomous characteristic on their opponents which defines two types for each player. In turn, each type has beliefs concerning her opponent's types, and payoffs are assumed to be type-independent. We analyze whether the mere possibility of different types playing different strategies generates discriminatory equilibria. Given a specific information structure we find that in equilibrium a player discriminates between her types if and only if her opponent does so. We also find that for dominant solvable 2x2 games no discriminatory equilibrium exists, while under different conditions of concordance between players' beliefs discrimination appears for coordination and for competitive games. A complete characterization of the set of Bayesian equilibria is provided.

Conditional independence in quantum many-body systems

In this thesis, I will discuss how information-theoretic arguments can be used to produce sharp bounds in the studies of quantum many-body systems. The main advantage of this approach, as opposed to the conventional field-theoretic argument, is that it depends very little on the precise form of the Hamiltonian. The main idea behind this thesis lies on a number of results concerning the structure of quantum states that are conditionally independent. Depending on the application, some of these statements are generalized to quantum states that are approximately conditionally independent. These structures can be readily used in the studies of gapped quantum many-body systems, especially for the ones in two spatial dimensions. A number of rigorous results are derived, including (i) a universal upper bound for a maximal number of topologically protected states that is expressed in terms of the topological entanglement entropy, (ii) a first-order perturbation bound for the topological entanglement entropy that decays superpolynomially with the size of the subsystem, and (iii) a correlation bound between an arbitrary local operator and a topological operator constructed from a set of local reduced density matrices. I also introduce exactly solvable models supported on a three-dimensional lattice that can be used as a reliable quantum memory.

Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

Energy Supply and the Sustainability of Endogenous Growth

29 p.

Numerical Studies of Topological Phases

The topological phases of matter have been a major part of condensed matter physics research since the discovery of the quantum Hall effect in the 1980s. Recently, much of this research has focused on the study of systems of free fermions, such as the integer quantum Hall effect, quantum spin Hall effect, and topological insulator. Though these free fermion systems can play host to a variety of interesting phenomena, the physics of interacting topological phases is even richer. Unfortunately, there is a shortage of theoretical tools that can be used to approach interacting problems. In this thesis I will discuss progress in using two different numerical techniques to study topological phases.

Recently much research in topological phases has focused on phases made up of bosons. Unlike fermions, free bosons form a condensate and so interactions are vital if the bosons are to realize a topological phase. Since these phases are difficult to study, much of our understanding comes from exactly solvable models, such as Kitaev's toric code, as well as Levin-Wen and Walker-Wang models. We may want to study systems for which such exactly solvable models are not available. In this thesis I present a series of models which are not solvable exactly, but which can be studied in sign-free Monte Carlo simulations. The models work by binding charges to point topological defects. They can be used to realize bosonic interacting versions of the quantum Hall effect in 2D and topological insulator in 3D. Effective field theories of "integer" (non-fractionalized) versions of these phases were available in the literature, but our models also allow for the construction of fractional phases. We can measure a number of properties of the bulk and surface of these phases.

Few interacting topological phases have been realized experimentally, but there is one very important exception: the fractional quantum Hall effect (FQHE). Though the fractional quantum Hall effect we discovered over 30 years ago, it can still produce novel phenomena. Of much recent interest is the existence of non-Abelian anyons in FQHE systems. Though it is possible to construct wave functions that realize such particles, whether these wavefunctions are the ground state is a difficult quantitative question that must be answered numerically. In this thesis I describe progress using a density-matrix renormalization group algorithm to study a bilayer system thought to host non-Abelian anyons. We find phase diagrams in terms of experimentally relevant parameters, and also find evidence for a non-Abelian phase known as the "interlayer Pfaffian".

Ab initio study of anharmonicity in high pressure Cmca-4 metallic hydrogen

Hydrogen is the only atom for which the Schr odinger equation is solvable. Consisting only of a proton and an electron, hydrogen is the lightest element and, nevertheless, is far from being simple. Under ambient conditions, it forms diatomic molecules H2 in gas phase, but di erent temperature and pressures lead to a complex phase diagram, which is not completely known yet. Solid hydrogen was rst documented in 1899 [1] and was found to be isolating. At higher pressures, however, hydrogen can be metallized. In 1935 Wigner and Huntington predicted that the metallization pressure would be 25 GPa [2], where molecules would disociate to form a monoatomic metal, as alkali metals that lie below hydrogen in the periodic table. The prediction of the metallization pressure turned out to be wrong: metallic hydrogen has not been found yet, even under a pressure as high as 320 GPa. Nevertheless, extrapolations based on optical measurements suggest that a metallic phase may be attained at 450 GPa [3]. The interest of material scientist in metallic hydrogen can be attributed, at least to a great extent, to Ashcroft, who in 1968 suggested that such a system could be a hightemperature superconductor [4]. The temperature at which this material would exhibit a transition from a superconducting to a non-superconducting state (Tc) was estimated to be around room temperature. The implications of such a statement are very interesting in the eld of astrophysics: in planets that contain a big quantity of hydrogen and whose temperature is below Tc, superconducting hydrogen may be found, specially at the center, where the gravitational pressure is high. This might be the case of Jupiter, whose proportion of hydrogen is about 90%. There are also speculations suggesting that the high magnetic eld of Jupiter is due to persistent currents related to the superconducting phase [5]. Metallization and superconductivity of hydrogen has puzzled scientists for decades, and the community is trying to answer several questions. For instance, what is the structure of hydrogen at very high pressures? Or a more general one: what is the maximum Tc a phonon-mediated superconductor can have [6]? A great experimental e ort has been carried out pursuing metallic hydrogen and trying to answer the questions above; however, the characterization of solid phases of hydrogen is a hard task. Achieving the high pressures needed to get the sought phases requires advanced technologies. Diamond anvil cells (DAC) are commonly used devices. These devices consist of two diamonds with a tip of small area; for this reason, when a force is applied, the pressure exerted is very big. This pressure is uniaxial, but it can be turned into hydrostatic pressure using transmitting media. Nowadays, this method makes it possible to reach pressures higher than 300 GPa, but even at this pressure hydrogen does not show metallic properties. A recently developed technique that is an improvement of DAC can reach pressures as high as 600 GPa [7], so it is a promising step forward in high pressure physics. Another drawback is that the electronic density of the structures is so low that X-ray di raction patterns have low resolution. For these reasons, ab initio studies are an important source of knowledge in this eld, within their limitations. When treating hydrogen, there are many subtleties in the calculations: as the atoms are so light, the ions forming the crystalline lattice have signi cant displacements even when temperatures are very low, and even at T=0 K, due to Heisenberg's uncertainty principle. Thus, the energy corresponding to this zero-point (ZP) motion is signi cant and has to be included in an accurate determination of the most stable phase. This has been done including ZP vibrational energies within the harmonic approximation for a range of pressures and at T=0 K, giving rise to a series of structures that are stable in their respective pressure ranges [8]. Very recently, a treatment of the phases of hydrogen that includes anharmonicity in ZP energies has suggested that relative stability of the phases may change with respect to the calculations within the harmonic approximation [9]. Many of the proposed structures for solid hydrogen have been investigated. Particularly, the Cmca-4 structure, which was found to be the stable one from 385-490 GPa [8], is metallic. Calculations for this structure, within the harmonic approximation for the ionic motion, predict a Tc up to 242 K at 450 GPa [10]. Nonetheless, due to the big ionic displacements, the harmonic approximation may not su ce to describe correctly the system. The aim of this work is to apply a recently developed method to treat anharmonicity, the stochastic self-consistent harmonic approximation (SSCHA) [11], to Cmca-4 metallic hydrogen. This way, we will be able to study the e ects of anharmonicity in the phonon spectrum and to try to understand the changes it may provoque in the value of Tc. The work is structured as follows. First we present the theoretical basis of the calculations: Density Functional Theory (DFT) for the electronic calculations, phonons in the harmonic approximation and the SSCHA. Then we apply these methods to Cmca-4 hydrogen and we discuss the results obtained. In the last chapter we draw some conclusions and propose possible future work.

On an embedding property of generalized Carter subgroups

If E and F are saturated formations, we say that E is strongly contained in F if for any solvable group G with E-subgroup, E, and F-subgroup, F, some conjugate of E is contained in F. In this paper, we investigate the problem of finding the formations which strongly contain a fixed saturated formation E.

Our main results are restricted to formations, E, such that E = {G|G/F(G) ϵT}, where T is a non-empty formation of solvable groups, and F(G) is the Fitting subgroup of G. If T consists only of the identity, then E=N, the class of nilpotent groups, and for any solvable group, G, the N-subgroups of G are the Carter subgroups of G.

We give a characterization of strong containment which depends only on the formations E, and F. From this characterization, we prove:

If T is a non-empty formation of solvable groups, E = {G|G/F(G) ϵT}, and E is strongly contained in F, then

(1) there is a formation V such that F = {G|G/F(G) ϵV}.

(2) If for each prime p, we assume that T does not contain the class, S_p’, of all solvable p’-groups, then either E = F, or F contains all solvable groups.

This solves the problem for the Carter subgroups.

We prove the following result to show that the hypothesis of (2) is not redundant:

If R = {G|G/F(G) ϵS_r’}, then there are infinitely many formations which strongly contain R.

Class two p groups as fixed point free automorphism groups

Suppose that AG is a solvable group with normal subgroup G where (|A|, |G|) = 1. Assume that A is a class two odd p group all of whose irreducible representations are isomorphic to subgroups of extra special p groups. If p^c ≠ r^d + 1 for any c = 1, 2 and any prime r where r^2d+1 divides |G| and if C_G(A) = 1 then the Fitting length of G is bounded by the power of p dividing |A|.

The theorem is proved by applying a fixed point theorem to a reduction of the Fitting series of G. The fixed point theorem is proved by reducing a minimal counter example. IF R is an extra spec r subgroup of G fixed by A₁, a subgroup of A, where A₁ centralizes D(R), then all irreducible characters of A₁R which are nontrivial on Z(R) are computed. All nonlinear characters of a class two p group are computed.

Relativistic quark models and the current algebra

In this thesis we are concerned with finding representations of the algebra of SU(3) vector and axial-vector charge densities at infinite momentum (the "current algebra") to describe the mesons, idealizing the real continua of multiparticle states as a series of discrete resonances of zero width. Such representations would describe the masses and quantum numbers of the mesons, the shapes of their Regge trajectories, their electromagnetic and weak form factors, and (approximately, through the PCAC hypothesis) pion emission or absorption amplitudes.

We assume that the mesons have internal degrees of freedom equivalent to being made of two quarks (one an antiquark) and look for models in which the mass is SU(3)-independent and the current is a sum of contributions from the individual quarks. Requiring that the current algebra, as well as conditions of relativistic invariance, be satisfied turns out to be very restrictive, and, in fact, no model has been found which satisfies all requirements and gives a reasonable mass spectrum. We show that using more general mass and current operators but keeping the same internal degrees of freedom will not make the problem any more solvable. In particular, in order for any two-quark solution to exist it must be possible to solve the "factorized SU(2) problem," in which the currents are isospin currents and are carried by only one of the component quarks (as in the K meson and its excited states).

In the free-quark model the currents at infinite momentum are found using a manifestly covariant formalism and are shown to satisfy the current algebra, but the mass spectrum is unrealistic. We then consider a pair of quarks bound by a potential, finding the current as a power series in 1/m where m is the quark mass. Here it is found impossible to satisfy the algebra and relativistic invariance with the type of potential tried, because the current contributions from the two quarks do not commute with each other to order 1/m³. However, it may be possible to solve the factorized SU(2) problem with this model.

The factorized problem can be solved exactly in the case where all mesons have the same mass, using a covariant formulation in terms of an internal Lorentz group. For a more realistic, nondegenerate mass there is difficulty in covariantly solving even the factorized problem; one model is described which almost works but appears to require particles of spacelike 4-momentum, which seem unphysical.

Although the search for a completely satisfactory model has been unsuccessful, the techniques used here might eventually reveal a working model. There is also a possibility of satisfying a weaker form of the current algebra with existing models.

Viscous layer meshes from level sets on cartesian meshes

The long term goal of our work is to enable rapid prototyping design optimization to take place on geometries of arbitrary size in a spirit of a real time computer game. In recent papers we have reported the integration of a Level Set based geometry kernel with an octree-based cut-Cartesian mesh generator, RANS flow solver and post-processing all within a single piece of software - and all implemented in parallel with commodity PC clusters as the target. This work has shown that it is possible to eliminate all serial bottlenecks from the CED Process. This paper reports further progress towards our goal; in particular we report on the generation of viscous layer meshes to bridge the body to the flow across the cut-cells. The Level Set formulation, which underpins the geometry representation, is used as a natural mechanism to allow rapid construction of conformal layer meshes. The guiding principle is to construct the mesh which most closely approximates the body but remains solvable. This apparently novel approach is described and examples given.

Reactive Many-Body Expansion for a Protonated Water Cluster.

We generalize the standard many-body expansion technique that is used to approximate the total energy of a molecular system to enable the treatment of chemical reactions by quantum chemical techniques. By considering all possible assignments of atoms to monomer units of the many-body expansion and associating suitable weights with each, we construct a potential energy surface that is a smooth function of the nuclear positions. We derive expressions for this reactive many-body expansion energy and describe an algorithm for its evaluation, which scales polynomially with system size, and therefore will make the method feasible for future condensed phase simulations. We demonstrate the accuracy and smoothness of the resulting potential energy surface on a molecular dynamics trajectory of the protonated water hexamer, using the Hartree-Fock method for the many-body term and Møller-Plesset theory for the low order terms of the many-body expansion.

Optimal specificity and function for flexible biomolecular recognition

Biomolecular associations often accompanied by large conformational changes, sometimes folding and unfolding. By exploring an exactly solvable model, we constructed the free energy landscape and established a general framework for studying the biomolecular flexible binding process. We derived an optimal criterion for the specificity and function for flexible biomolecular binding where the binding and conformational folding are coupled.

Optimal specificity and function for flexible biomolecular recognition

Biomolecular associations often accompanied by large conformational changes, sometimes folding and unfolding. By exploring an exactly solvable model, we constructed the free energy landscape and established a general framework for studying the biomolecular flexible binding process. We derived an optimal criterion for the specificity and function for flexible biomolecular binding where the binding and conformational folding are coupled.