We study minimization problems with respect to a one-parameter family of generalized relative entropies. These relative entropies, which we call relative -entropies (denoted I (P; Q)), arise as redundancies under mismatched compression when cumulants of compression lengths are considered instead of expected compression lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative -entropies behave like squared Euclidean distance and satisfy the Pythagorean property. We explore the geometry underlying various statistical models and its relevance to information theory and to robust statistics. The thesis consists of three parts. In the first part, we study minimization of I (P; Q) as the first argument varies over a convex set E of probability distributions. We show the existence of a unique minimizer when the set E is closed in an appropriate topology. We then study minimization of I on a particular convex set, a linear family, which is one that arises from linear statistical constraints. This minimization problem generalizes the maximum Renyi or Tsallis entropy principle of statistical physics. The structure of the minimizing probability distribution naturally suggests a statistical model of power-law probability distributions, which we call an -power-law family. Such a family is analogous to the exponential family that arises when relative entropy is minimized subject to the same linear statistical constraints. In the second part, we study minimization of I (P; Q) over the second argument. This minimization is generally on parametric families such as the exponential family or the - power-law family, and is of interest in robust statistics ( > 1) and in constrained compression settings ( < 1). In the third part, we show an orthogonality relationship between the -power-law family and an associated linear family. As a consequence of this, the minimization of I (P; ), when the second argument comes from an -power-law family, can be shown to be equivalent to a minimization of I ( ; R), for a suitable R, where the first argument comes from a linear family. The latter turns out to be a simpler problem of minimization of a quasi convex objective function subject to linear constraints. Standard techniques are available to solve such problems, for example, via a sequence of convex feasibility problems, or via a sequence of such problems but on simpler single-constraint linear families.

<p dir="ltr">Since graphs are natural representations for encoding relational data, the problem of graph matching is an emerging task and has attracted increasing attention, which could potentially impact various domains such as social network de-anonymization and computer vision. Our main interest is designing polynomial-time algorithms for seeded graph matching problems where a subset of pre-matched vertex-pairs (seeds) is revealed. </p><p dir="ltr">However, the existing work does not fully investigate the pivotal role of seeds and falls short of making the most use of the seeds. Notably, the majority of existing hand-crafted algorithms only focus on using ``witnesses'' in the 1-hop neighborhood. Although some advanced algorithms are proposed to use multi-hop witnesses, their theoretical analysis applies only to \ER random graphs and requires seeds to be all correct, which often do not hold in real applications. Furthermore, a parallel line of research, Graph Neural Network (GNN) approaches, typically employs a semi-supervised approach, which requires a large number of seeds and lacks the capacity to distill knowledge transferable to unseen graphs.</p><p dir="ltr">In my dissertation, I have taken two approaches to address these limitations. In the first approach, we study to design hand-crafted algorithms that can properly use multi-hop witnesses to match graphs. We first study graph matching using multi-hop neighborhoods when partially-correct seeds are provided. Specifically, consider two correlated graphs whose edges are sampled independently from a parent \ER graph $\mathcal{G}(n,p)$. A mapping between the vertices of the two graphs is provided as seeds, of which an unknown fraction is correct. We first analyze a simple algorithm that matches vertices based on the number of common seeds in the $1$-hop neighborhoods, and then further propose a new algorithm that uses seeds in the $D$-hop neighborhoods. We establish non-asymptotic performance guarantees of perfect matching for both $1$-hop and $2$-hop algorithms, showing that our new $2$-hop algorithm requires substantially fewer correct seeds than the $1$-hop algorithm when graphs are sparse. Moreover, by combining our new performance guarantees for the $1$-hop and $2$-hop algorithms, we attain the best-known results (in terms of the required fraction of correct seeds) across the entire range of graph sparsity and significantly improve the previous results. We then study the role of multi-hop neighborhoods in matching power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to use the seeds to recover the remaining latent vertex correspondence between the two graphs. Departing from the existing approaches that focus on the use of high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Our result achieves an exponential reduction in the seed size requirement compared to the best previously known results.</p><p dir="ltr">In the second approach, we study GNNs for seeded graph matching. We propose a new supervised approach that can learn from a training set how to match unseen graphs with only a few seeds. Our SeedGNN architecture incorporates several novel designs, inspired by our theoretical studies of seeded graph matching: 1) it can learn to compute and use witness-like information from different hops, in a way that can be generalized to graphs of different sizes; 2) it can use easily-matched node-pairs as new seeds to improve the matching in subsequent layers. We evaluate SeedGNN on synthetic and real-world graphs and demonstrate significant performance improvements over both non-learning and learning algorithms in the existing literature. Furthermore, our experiments confirm that the knowledge learned by SeedGNN from training graphs can be generalized to test graphs of different sizes and categories.</p>

<p>Holographic duality as a rigorous approach to quantum gravity claims that a quantum gravitational system is exactly equal to a quantum theory without gravity in lower spacetime dimensions living on the boundary of the quantum gravitational system. The duality maps key questions about the emergence of spacetime to questions on the non-gravitational boundary system that are accessible to us theoretically and experimentally. Recently, various aspects of quantum information theory on the boundary theory have been found to be dual to the geometric aspects of the bulk theory. In this thesis, we study the exact and approximate quantum error corrections (QEC) in a general quantum system (von Neumann algebras) focused on QFT and gravity. Moreover, we study entanglement theory in the presence of conserved charges in QFT and the multiparameter multistate generalization of quantum relative entropy.</p>

The idea of holography [1, 2] finds a concrete realization in form of the AdS/CFT correspondence [3, 4]. This duality relates a field theory with conformal symmetries to quantum gravity living in one higher dimension. In this thesis we study aspects of black hole quasinormal modes, higher spin theories and entanglement entropy in the context of this duality. In almost all cases we have been able to subject the duality to some precision tests. Quasinormal modes encode the spectrum of black holes and the time-scale of pertur- bations therein [5]. From the dual CFT viewpoint they are the poles of retarded Green's function (or peaks in the spectral function) [6]. Quasinormal modes were previously studied for scalar, gauge field and fermion fluctuations [7]. We solve for these quasinormal modes of higher spin (s _ 2) fields in the background of the BTZ black hole [8, 9]. We obtain an exact solution for a field of arbitrary spin s (integer or half-integer) in the BTZ background. This implies that the BTZ is perhaps the only known black hole background where such an analysis can be done analytically for all bosonic and fermionic fields. The quasinormal modes are shown to match precisely with the poles of the corresponding Green's function in the CFT living on the boundary. Furthermore, we show that one-loop determinants of higher spin fields can also be written as a product form [10] in terms of these quasinormal modes and this agrees with the same obtained by integrating the heat-kernel [11]. We then turn our attention to dualities relating higher-spin gravity to CFTs with W algebra symmetries. Since higher spin gravity does go beyond diffeomorphism invariance, one needs re_ned notions of the usual concepts in differential geometry. For example, in general relativity black holes are defined by the presence of the horizon. However, higher spin gravity has an enlarged group of symmetries of which the diffeomorphisms form a subgroup. The appropriate way of thinking of solutions in higher spin gravity is via characterizations which are gauge invariant [12, 13]. We study classical solutions embedded in N = 2 higher spin supergravity. We obtain a general gauge-invariant condition { in terms of the odd roots of the superalgebra and the eigenvalues of the holonomy matrix of the background { for the existence of a Killing spinor such that these solutions are supersymmetric [14]. We also study black holes in higher spin supergravity and show that the partition function of these black holes match exactly with that obtained from a CFT with the same asymptotic symmetry algebra [15]. This involved studying the asymptotic symmetries of the black hole and thereby developing the holographic dictionary for the bulk charges and chemical potentials with the corresponding quantities of the CFT. We finally investigate entanglement entropy in the AdS3/CFT2 context. Entanglement entropy is an useful non-local probe in QFT and many-body physics [16]. We analytically evaluate the entanglement entropy of the free boson CFT on a circle at finite temperature (i.e. on a torus) [17]. This is one of the simplest and well-studied CFTs. The entanglement entropy is calculated via the replica trick using correlation functions of bosonic twist operators on the torus [18]. We have then set up a systematic high temperature expansion of the Renyi entropies and determined their finite size corrections. These _nite size corrections both for the free boson CFT and the free fermion CFT were then compared with the one-loop corrections obtained from bulk three dimensional handlebody spacetimes which have higher genus Riemann surfaces (replica geometry) as its boundary [19]. One-loop corrections in these geometries are entirely determined by the spectrum of the excitations present in the bulk. It is shown that the leading _nite size corrections obtained by evaluating the one-loop determinants on these handlebody geometries exactly match with those from the free fermion/boson CFTs. This provides a test for holographic methods to calculate one-loop corrections to entanglement entropy. We also study conformal field theories in 1+1 dimensions with W-algebra symmetries at _nite temperature and deformed by a chemical potential (_) for a higher spin current. Using OPEs and uniformization techniques, we show that the order _2 correction to the Renyi and entanglement entropies (EE) of a single interval in the deformed theory is universal [20]. This universal feature is also supported by explicit computations for the free fermion and free boson CFTs { for which the EE was calculated by using the replica trick in conformal perturbation theory by evaluating correlators of twist fields with higher spin operators [21]. Furthermore, this serves as a verification of the holographic EE proposal constructed from Wilson lines in higher spin gravity [22, 23]. We also examine relative entropy [24] in the context of higher-spin holography [25]. Relative entropy is a measure of distinguishability between two quantum states. We confirm the expected short-distance behaviour of relative entropy from holography. This is done by showing that the difference in the modular Hamiltonian between a high-temperature state and the vacuum matches with the difference in the entanglement entropy in the short-subsystem regime.

Social networks play an important role in disseminating a piece of information in a population. Companies advertising a newly launched product, movie promotion, political campaigns, social awareness campaigns by governments, charity campaigns by NGOs and crowd funding campaigns by entrepreneurs are a few examples where an entity is interested in disseminating a piece of information in a target population, possibly under resource constraints. In this thesis we model information diffusion in a population using various epidemic models and study optimal campaigning strategies to maximize the reach of information. In the different problems considered in this thesis, information epidemics are modeled as the Susceptible-Infected, Susceptible-Infected-Susceptible, Susceptible-Infected-Recovered and Maki Thompson epidemic processes; however, we modify the models to incorporate the intervention made by the campaigner to enhance information propagation. Direct recruitment of individuals as spreaders and providing word-of-mouth incentives to the spreaders are considered as two intervention strategies (controls) to enhance the speed of information propagation. These controls can be implemented by placing advertisements in the mass media, announcing referral/cash back rewards for introducing friends to a product or service being advertised etc. In the different problems considered in this thesis, social contacts are modeled with varying levels of complexity---population is homogeneously mixed or follows heterogeneous mixing. The solutions to the problems which consider homogeneous mixing of individuals identify the most important periods in the campaign duration which should be allocated more resources to maximize the reach of the message, depending on the system parameters of the epidemic model (e.g., epidemics with high and low virulence). When a heterogeneous model is considered, apart from this, the solution identifies the important classes of individuals which should be allocated more resources depending upon the network considered (e.g. Erdos-Renyi, scale-free) and model parameters. These classes may be carved out based on various centrality measures in the network. If multiple strategies are available for campaigning, the solution also identifies the relative importance of the strategies depending on the network type. We study variants of the optimal campaigning problem where we optimize different objective functions. For some of the formulated problems, we discuss the existence and uniqueness of the solution. Sometimes our formulations call for novel techniques to prove the existence of a solution.