In this dissertation we study concentration properties of Markov chains,and sequential decision making problems which involve stochastic modeling with Markov chains.

We start by developing a simple yet powerful Hoeffding inequality for Markovian sums under only the irreducibility assumption.To illustrate its usefulness we provide two applications in multi-armed bandit problems. The first is about identifying an approximately best Markovian arm, while the second is concerned with regret minimization in the context of Markovian bandits, generalizing two well known algorithms from the i.i.d. case.

We proceed with the study of the concentration properties of a Lipschitz function applied to a Markov chain,which form a generalization of Hoeffding's inequality. In particular we investigate a transportation problem that arises naturally when the martingale method is applied. The so called bicausal optimal transport problem for Markov chains, is an optimal transport formulation suitable for stochastic processes which takes into consideration the accumulation of information as time evolves. Our analysis is based on a relation between the transport problem and the theory of Markov decision processes. This way we are able to derive necessary and sufficient conditions for optimality in the transport problem, as well as an iterative algorithm, namely the value iteration, for the calculation of the transportation cost. Additionally, we draw the connection with the classic theory on couplings for Markov chains, and in particular with the notion of faithful couplings.

Next we focus on a finite-sample analysis of large deviation results for Markov chains.First we study the exponential family of stochastic matrices, which serve as a change of measure, and we develop conditions under which the asymptotic Perron-Frobenius eigenvector stays strictly positive. This leads to a Chernoff bound which attains a constant prefactor and an exponential decay with the optimal large deviations rate. Moreover, a finite-sample version of the law of the iterated logarithm is derived, and a uniform multiplicative ergodic theorem for the exponential family of tilted transition probability matrices is established.

On the applications side, we give a complete characterization of the sampling complexityof best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which generalizing those of the i.i.d. setting, and we analyze the Track-and-Stop strategy, proving that asymptotically it is at most a factor of four apart from the lower bound.

We conclude with with an extension of the classic stochastic multi-armed bandit problem which involves multiple plays and Markovian rewards in the rested bandits setting.In order to tackle this problem we consider an adaptive allocation rule which at each stage combines the information from the sample means of all the arms, with the Kullback-Leibler upper confidence bound of a single arm which is selected in round-robin way. For rewards generated from a one-parameter exponential family of Markov chains, we provide a finite-time upper bound for the regret incurred from this adaptive allocation rule, which reveals the logarithmic dependence of the regret on the time horizon, and which is asymptotically optimal. As a byproduct of our analysis we also establish asymptotically optimal, finite-time guarantees for the case of multiple plays, and i.i.d. rewards drawn from a one-parameter exponential family of probability densities. Finally, we provide simulation results that illustrate that calculating Kullback-Leibler upper confidence bounds in a round-robin way, is significantly more efficient than calculating them for every arm at each round, and that the expected regrets of those two approaches behave similarly.

Graph partitioning problems are a central topic of research in the study of approximation algorithms. They are of interest to theoretical computer scientists for their far-reaching connections to spectral graph theory, metric embeddings and inapproximability theory. And they are also important for many practitioners, as algorithms for graph partitioning are often fundamental primitives in the solution of other problems, such as image segmentation, clustering and social-network analysis.

While many theoretical approximation algorithms exist for graph partitioning, they often rely on multicommodity-flow computations that run quadratic time in the worst case and are too time-consuming for the massive graphs that are prevalent in today's applications. In this thesis, we study the design of approximation algorithms that yield strong approximation ratios, while running in subquadratic time and relying on computational procedures that are often fast in practice.

Our algorithms employ spectral and s-t flow operations to explore the cuts of a graph in a very efficient way. A crucial ingredient in their design is the usage of random walks that capture the sparse cuts of a graph better than single eigenvectors. The analysis of our methods is particularly simple, as it relies on a semidefinite programming formulation of the graph partitioning problem of choice. Indeed, we can develop our algorithms as primal-dual methods for solving a semidefinite program and show that certain random walks arise naturally from this approach.

Differential privacy is the now de facto industry standard for ensuring privacy while publicly releasing statistics about a sensitive database. At a high level, differentially private algorithms add noise to the statistics they compute, so an adversary cannot with high confidence guess if any individual is in the database as any individual's effect on the statistics can be replicated by the noise.

The fundamental paradigm in differential privacy is the privacy-accuracy trade-off: A differentially private algorithm's output can be made more accurate by reducing the amount of noise added, but in doing so the privacy guarantee decays. Current state-of-the-art algorithms often require practitioners to choose between a large drop in accuracy compared to non-private algorithms, or very weak privacy guarantees. Improving the trade-off between privacy, accuracy, would ideally allow practitioners to get the ``best of both worlds.'' Sometimes, efficiency is also traded off with privacy and accuracy. That is, despite differential privacy being an information-theoretic guarantee, an inefficient (and thus impractical to implement) algorithm may still obtain a better privacy-accuracy trade-off than the best known efficient algorithm. Designing efficient algorithms that match the privacy-accuracy trade-off of known inefficient algorithms thus is also of practical importance.

In this thesis, we consider counting queries, private log-strongly concave sampling, and private convex optimization, all fundamental problems in sampling and optimization, and give algorithms for each problem improving the privacy-accuracy trade-off or efficiency when compared to the previous state of the art algorithms. For counting queries, we show that adding noise from a ``Generalized Gaussian'' gives better worst-case accuracy compared to Gaussian noise. For private log-strongly concave sampling, we show that the discrete Langevin dynamics allows one to efficiently approximately sample from a target distribution while preserving privacy, a commonly needed primitive in private optimization. For private convex optimization, we show that in some settings (including e.g. private linear regression), if we are given a sufficient amount of public data, we can obtain a better dependence on the dimensionality of the problem than differentially private gradient descent.

Positive linear programs (LPs), or equivalently, mixed packing and covering LPs, are LPs formulated with

non-negative coefficients, constants, and variables. Notable special cases of positive LPs include packing LPs and covering LPs. Positive LPs model a wide range of fundamental problems both in theory of computation as well as in practice, thus have long drawn interest in theoretical computer science, operations research, and optimization communities.

In this work, we study iterative methods for approximately solving positive LPs efficiently. Given a positive LP of size $N$, we are interested in iterative methods that can converge to a $(1\pm \epsilon)$-approximate optimal solution with complexity that is nearly linear in $N$, and polynomial in $\frac{1}{\epsilon}$.

For the special cases of packing LPs and covering LPs, we design improved sequential and parallel approximate solvers, both using first-order (i.e. gradient based) descent methods from (continuous) convex optimization. In particular, we build upon the linear coupling framework introduced by Allen-Zhu and Orecchia. The performance of first-order methods are sensitive to the geometry of the problem space, as well as properties of the objective function. At a high level, we design (discrete) techniques that exploit the combinatorial structures of the LPs, which lead to significantly improved theoretical behavior of the optimization method. More specifically, our sequential (i.e., non-parallelizable) solver is based on a $\tilde{O}(N/\epsilon)$ algorithm for packing LPs in a previous breakthrough by Allen-Zhu and Orecchia, and we provide a unified method with running time $\tilde{O}(N/\epsilon)$ for both packing LPs and covering LPs. Our parallel algorithm has depth (i.e., parallel running time) $\tilde{O}(1/\epsilon^2)$, which is $\Omega(1/\epsilon)$ faster than the previous best algorithm.

For general positive LPs, we take a more combinatorial framework, called Lagrangian relaxation, but we crucially adapt the framework to leverage insights from continuous convex optimization. The incorporation of continuous optimization techniques provides a primal-dual perspective of the method, and leads to faster convergence. More specifically, we develop a $\tilde{O}(1/\epsilon^3)$ depth parallel algorithm, improving a long-standing bound of $\tilde{O}(1/\epsilon^4)$ for positive LPs.

At a high level, we benefit from a integrated view of continuous and combinatorial techniques to obtain the improved results in this work. This combination brings intriguing new perspectives to algorithm design, and is promising for further exciting progress.

High-dimensional expansion, a generalization of graph expansion to higher-order edges, has recently garnered significant attention in the theoretical computer science community for the additional boost they give in applications like error-correction and approximate sampling. In this thesis, we explore two problems related to high-dimensional expansion, using tools from the geometry of polynomials as well as high-dimensional convex geometry.

First, we study approximate sampling from discrete distributions. The framework for sampling obtained from high-dimensional expansion provides both a natural set of random walks to use in MCMC algorithms, as well as a set of tools for their analysis. We show that the geometric properties (e.g. log-concavity) of a polynomial derived from the distribution allows us to speed up the implementations of these random walks.

Next, we study a random graph model called the ``random geometric graph,'' with an eventual goal of understanding its modeling capabilities as well as its high-dimensional expansion properties. Along the way, we prove new results about distinguishing the random geometric graph model from the Erdos-Renyi model, and develop a new geometric toolkit for analyzing these graphs.

This dissertation discusses how to write efficient, deterministic

programs to infer phylogenetic trees. These programs are based on a

theoretically optimal polynomial time algorithm. The programs are

practical and efficient.

The problem is to infer phylogenetic trees from sequence data at the

leaves. Likelihood approaches attempt to solve an NP-complete

optimization problem, and are computationally intense.

Our approach is to apply efficient, polynomial time algorithms which

are provably accurate to within a constant factor of optimal.

We present a program which is practical and computationally efficient.

We study data-efficient and also practical de-novo genome assembly algorithm. Due to the advancement in high-throughput sequencing, the cost of read data has gone down rapidly in recent years. Thus, there is a growing need to do genome assembly in a cost effective manner on a large scale. However, the state-of-the-art assemblers are not designed to be data-efficient. This leads to wastage of read data, which translates to a significant monetary loss for large scale sequencing projects. Moreover, as technology advances, the nature of the read data also evolves. This makes the old assemblers insufficient for discovering all the information behind the data. Therefore, there is a need to re-invent genome assemblers to suit the growing demand.

In this dissertation, we address the data efficiency aspect of genome assembly as follows.

First, we show that even when there is noise in the reads, one can successfully reconstruct the genomes with information requirements close to the noiseless fundamental limit. We develop a new assembly algorithm, X-phased Multibridging, is designed based on a probabilistic model of the genome. We show, through analysis that it performs well on the model, and through simulation that it performs well on real genomes.

Second, we introduce FinisherSC, a repeat-aware and scalable tool for upgrading de-novo haploid genome assembly using long and noisy reads. Experiments with real data suggest that FinisherSC can provide longer and higher quality contigs than existing tools while maintaining high concordance. Thus, FinisherSC achieves higher data efficiency than state-of-the-art haploid genome assembly pipelines.

Third, we study whether post-processing metagenomic assemblies with the original input long reads can result in quality improvement. Previous approaches have focused on pre-processing reads and optimizing assemblers. We introduce BIGMAC, which takes an alternative perspective to focus on the post-processing step. Using both the assembled contigs and original long reads as input, BIGMAC first breaks the contigs at potentially mis-assembled locations and subsequently scaffolds contigs. Our experiments on metagenomes assembled from long reads show that BIGMAC can improve assembly quality by reducing the number of mis-assemblies while maintaining/increasing N50 and N75. Thus, BIGMAC achieves higher data efficiency than state-of-the-art metagenomic assembly pipelines.

Moreover, we also discuss some theoretical work regarding genome assembly in terms of data, time and space efficiency; and a promising post-processing tool POSTME in improving metagenomic assembly using both short and long reads.

The Asymmetric Traveling Salesman Problem and its variants are optimization problems that are widely studied from the viewpoint of approximation algorithms as well as hardness of approximation. The natural LP relaxation for ATSP has been conjectured to have an $O(1)$ integrality gap. Recently the best known approximation factor for this problem was improved from the decades-old $O(\log(n))$ to $O(\log(n)/\log\log(n))$ using the connection between ATSP and Goddyn's Thin Tree conjecture.

In this work we show that the integrality gap of the famous Held-Karp LP relaxation for ATSP is bounded by $\log\log(n)^{O(1)}$ which entails a polynomial time $\log\log(n)^{O(1)}$-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a $\log\log(n)^{O(1)}$ factor, but does not provide a solution with that cost. This is one of the very few instances of natural problems studied in approximation algorithms where the state of the art approximation and estimation algorithms do not match.

We prove this by making progress on Goddyn's Thin Tree conjecture; we show that every $k$-edge-connected graph contains a $\log\log(n)^{O(1)}/k$-thin tree.

To tackle the Thin Tree conjecture, we build upon the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava. We answer the following question by providing sufficient conditions: Given a set of rank 1 quadratic forms, can we select a subset of them from a given collection of subsets, whose total sum is bounded by a fraction of the sum of all rank 1 quadratic forms?

Finally we address the problem of designing polynomial time approximation algorithms, algorithms that also output a solution, matching the guarantee of the estimation algorithm. We prove that this entirely relies on finding a polynomial time algorithm for our extension of the Kadison-Singer problem. Namely we prove that ATSP can be $\log(n)^\epsilon$-approximated in polynomial time for any $\epsilon>0$ and that it can be $\log\log(n)^{O(1)}$-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.

Communication now is easier than ever before. One consequence of this is the emergence of virtual communities, unconstrained by physical proximity. We perform two investigations into changing social trends. We study a corpus of 100 years of newspaper articles to see if we can find evidence to support the popular intuition that as news cycles have sped up, the public's attention span has gotten shorter. We find no such evidence: to the contrary, we find that the typical length of time that a person's name stays in the news has not changed over time, and celebrities now stay in the news for longer than ever before. We also investigate a new kind of community on Twitter called a group chat, where members have regular meetings to discuss a broad range of topics, from medical conditions to hobbies. We find that the phenomenon is growing over time, and paint a broad picture of the topics which one could find a group chat to discuss. With a view to helping connect new participants to group chats they may not have been able to find or might not have been aware of, we design an algorithm to rank group chats in the context of a topic given as a query.

We study the Sum-of-Squares semidefinite programming hierarchy via the lens of average-case problems.

The Sum-of-Squares Hierarchy is a formulaic family of convex relaxations to polynomial optimization problems, which allows one to trade runtime for accuracy in a smooth manner. The Hierarchy has been studied since the early 2000’s, both from the perspective of optimization and control and as a proof system. In the past five years, the Hierarchy has become a focus of intensive study in the theory of computation community. This is because recent results give us reason to hope that Sum-of-Squares algorithms may refute important

conjectures on hardness of approximation. However, our understanding of the guarantees of the Hierarchy remains relatively incomplete.

In this dissertation, we present three results which make modest progress towards understanding the power and limitations of the Sum-of-Squares Hierarchy; all three works use average-case problems as a lens for the Sum-of-Squares algorithms, by enabling us to use

random matrix theory as a tool in the analysis.

First, we analyze the performance of the Hierarchy for strongly refuting random constraint satisfaction problems (CSPs). We obtain a full characterization of the Sum-of-Squares Hierarchy for strong refutation of random CSPs, and give new subexponential-time strong

refutation algorithms for CSPs with super-linear density.

Next, we give impossibility results for solving the planted clique problem via a Sum-of-Squares algorithm, demonstrating that the degree-4 Sum-of-Squares algorithm cannot distinguish graphs which contain a planted clique from uniformly random graphs.

Finally, even in the asymptotically polynomial-time regime, the Sum-of-Squares algorithm is often prohibitively slow. We show that for average-case problems, polynomial-time Sum-of-Squares algorithms can often be replaced with fast spectral algorithms, which run in linear or near-linear time in the input size.