While computing algebraic K-theory groups is often very difficult, understanding fixed point spectra of topological Hochschild homology can aid in such computations. Taking homotopy groups of these spectra, we arrive at TR-groups, an integer-graded theory with a rigid algebraic structure. By understanding TR-groups, one can compute topological cyclic homology, and consequently, algebraic K-theory. This homotopy theoretic approach to algebraic K- theory has been very fruitful.

For many algebraic K-theory computations, however, it is beneficial to further exploit the S¹-equivariant structure of topological Hochschild homology. The topological Hochschild S¹-spectrum has naturally associated equivariant homotopy groups graded by the real rep- resentation ring of S¹, which provide an RO(S¹)-graded TR-theory.

In this talk we will review classical TR-theory, and introduce the RO(S¹)-graded analog and its applications to algebraic K-theory. The main result will be the explicit computation of the RO(S¹)-graded equivariant homotopy of THH(F_p ). This computation of TRⁿ_a(F_p;p) extends a result of Hesselholt and Madsen to provide the first complete computation of RO(S¹)-graded TR-groups. In particular, we compute the groups TRⁿ_q+a(F_p;p) for q even, and the order of these groups for q odd.

In this thesis a conjecture of Okounkov, a conjecture of Fomin-Fulton-Li-Poon, and a special case of Lascoux-Leclerc-Thibon's conjecture on Schur positivity of certain differences of products of Schur functions are proved. In the first part of the work a combinatorial method is developed that allows to prove weaker versions of those conjectures. In the second part a recent result of Rhoades and Skandera is used to provide a proof of actual Schur positivity results. Several further generalizations are stated and proved. In particular, an intriguing log-concavity property of Schur functions is observed. In addition, a stronger conjecture is stated in language of alcoved polytops. A weaker version of this conjecture is proved using a characterization of Klyachko cone and the theory of Temperley-Lieb immanants.

We give nontrivial upper and lower bounds for the total number of distinct degree sequences among all simple, unlabeled graphs on n vertices (graphical partitions on n vertices). Our upper bound is
4ⁿ /(log n)^C √n for some constant C, an improvement of (log n)^C over the trivial upper bound which is asymptotic to 4ⁿ /2√πn. Our lower bound is 4ⁿ /Cn, an improvement of √n over the trivial lower bound which is asymptotic to 4ⁿ /Cn^3/2.

The classical Brill-Noether theorems count the dimension of the family of maps from a general curve of genus g to non-degenerate curves of degree d in an r-dimensional projective space. These theoerems can be extended to include ramification conditions at fixed general points.

This thesis deals with the problem of imposing a ramification condition at an unspecified point. We solve the problem completely in dimension 1, prove a closed-form existence criterion and a finiteness result in dimension 2, and provide an existence test and bound the dimension of the family in the general case.

In the first part, we present a family of entanglement purification protocols that generalize four previous methods, namely the recurrence method, the modified recurrence method, and the two methods proposed by Maneva-Smolin and Leung-Shor. We will show that this family of protocols have improved yields over a wide range of initial fidelities F, and hence imply new lower bounds on the quantum capacity assisted by two-way classical communication of the quantum depolarizing channel. In particular, we show that the yields of these protocols are higher than the yield of universal hashing for F less than 0.993 and as F goes to 1.

In the second part, we define, for any quantum discrete memoryless channel, quantum entanglement capacity with classical feedback, a quantity that lies between two other well-studied quantities. These two quantities - namely the quantum capacity assisted by two-way classical communication and the quantum capacity with classical feedback - are widely conjectured to be different. We then present adaptive protocols for this newly-defined quantity on the quantum depolarizing channel. These protocols in turn imply new lower bounds on the quantum capacity with classical feedback.

In this thesis, we consider several parabolic equations for which the minimal principle fails. We first consider a two-point boundary value problem for a one dimensional diffusion equation. We show the uniqueness and existence of the solution for initial data, which may not be continuous at two boundary points. We also examine the circumstances when these solutions admit a probabilistic interpretation. Some partial results are given for analogous problems in more than one dimension.

Graph states are quantum states (quantum codes) in qⁿ -dimensional space (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, F_q . Graph states are determined as a common eigenvector of independent elements of the n-folded Pauli group, on which local Clifford group has a natural actions. This action induces the natural action of local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. Two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of local Clifford group mapping one graph to the other one.

We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F_q . In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not.

Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that in general (for either cases q being odd or even), the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to , which is computationally as large as the total number of graphs.

We consider the problem of computing the order of an element in a generic group. This is known to require exponential time. The two standard algorithms, Pollard’s rho method and Shanks’ baby-steps giant-steps technique, both use Θ (N^1/2) group operations to compute
|α| = N, and a lower bound of Ω (N^1/2) has been conjectured. We disprove this conjecture, presenting a generic algorithm with complexity o (N^1/2) in any group. The worst case occurs when G is a cyclic group of (unknown) prime order, but for approximately half the integers N ε [0,M], the complexity is O (N^1/3).

We prove that a generic algorithm can perform any number of order computations in near linear time, plus the cost of a single order computation with N = λ(G), where λ(G) is the group exponent (without knowledge of λ(G)). We show that in abelian groups, λ(G) can be computed for the same cost, and also consider some non-abelian cases.

We then use λ(G) to compute the structure of an abelian group. Given an O (N^2-ε) bound on |G| = N, we can compute group structure in o (N^1/2) group operations for all but a small set of pathological cases. The complexity is essentially that of an order computation on a single random element. A lower bound of Ω (N^1/2) had been assumed, based on a similar bound for the discrete logarithm problem.

We apply these results to compute the ideal class groups of imaginary quadratic number fields, a standard test case for generic algorithms. In [2], Teske reports computing the class group for discriminant −4(10³⁰ + 1) over the course of 15 days on a SparcStation4 using a generic algorithm. We accomplish the same task in less than 8 seconds on an Intel PC. Comparisons with non-generic algorithms for class group computation are also favorable. Buchmann et al. used a subexponential algorithm to compute the class group for discriminant −4(10⁵⁴+ 1) in less than 9 hours on a SparcUltra1, beating the previous record of 10 days [1]. We compute the same class group in less than 30 seconds.

Data for these and many previously uncomputed class groups are presented, along with results for elliptic curves and some non-abelian groups. As an example, we are pleased to report that the class group for quadratic discriminant −4(10⁶⁰+ 1) is, with high probability,

Quasi-categories were introduced by Boardman and Vogt, then more recently named and developed by Joyal, Lurie, and others. The model theory of quasi-categories can be thought of as a model of the homotopy theory of homotopy theories, alongside e.g. complete Segal spaces and simplicially enriched categories. Quasi-categories have the advantage, however, of functioning theoretically much like ordinary categories, as well as being functionally extremely simple (they are just simplicial sets satisfying the inner horn-filling condition).

It is the goal of this talk to discuss one such similarity, namely the notion of quasi-category fibred in Kan complexes (what one might call quasi-category fibred in quasi-groupoids, and what in practice is known as a right fibration). Not only do these objects generalize Grothendieck's categories fibred in groupoids, the quasi-category of right fibrations over a given base simplicial set $S$ can be constructed as having $n$-simplices being all right fibrations over $S\times\Delta^n$. Thus, the quasi-cateogry of right fibrations can be thought of as a quasi-cateogry which arises "naturally" (as opposed to as the coherent nerve of a category enriched in Kan complexes, for example). Constructing the quasi-category this way also means this quasi-category classifies families of right fibrations up to \emph{isomorphism} (not just homotopy equivalence).

If there is time, we will also discuss how (homotopy) limits and the Yoneda functor can be constructed directly using this formalism.

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in ⁿ (the current best algorithm has complexity roughly n⁴ , conjectured to be n³). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.

We also consider the problem of computing the centroid of a convex body in ⁿ . We prove that if the body is a polytope given as an intersection of half-spaces, then computing the centroid exactly is #P -hard, even for order polytopes, a special case of 0–1 polytopes. We also prove that if the body is given by a membership oracle, then for any deterministic algorithm that makes a polynomial number of queries there exists a body satisfying a roundedness condition such that the output of the algorithm is outside a ball of radius σ/100 around the centroid, where σ² is the minimum eigenvalue of the inertia matrix of the body.

Finally, we consider the problem of determining whether a given set S in ⁿ is approximately convex, i.e., if there is a convex set K ε ⁿ such that the volume of their symmetric difference is at most ε vol(S ) for some given ε. When the set is presented only by a membership oracle and a random oracle, we show that the problem can be solved with high probability using poly(n)(c/ε)ⁿ oracle calls and computation time. We complement this result with an exponential lower bound for the natural algorithm that tests convexity along “random” lines. We conjecture that a simple 2-dimensional version of this algorithm has polynomial complexity.

Can one compute a low-dimensional representation of any given data by looking only at its small sample, chosen cleverly on the fly?

Motivated by the above question, we consider the problem of low-rank matrix approximation: given a matrix A ε ^m×n, one wants to compute a rank-k matrix (where ) nearest to A in the Frobenius norm (also known as the Hilbert-Schmidt norm). We prove that using a sample of roughly O(k/ε) rows of A one can compute, with high probability, a (1 + ε)- approximation to the nearest rank-k matrix. This gives an algorithm for low-rank approximation with an improved error guarantee (compared to the additive guarantee known earlier from the work of Frieze, Kannan, and Vempala) and running time
O(M k/ε), where M is the number of non- zero entries of A. The proof is based on two sampling techniques called adaptive sampling and volume sampling, and some linear algebraic tools.

Low-rank matrix approximation under the Frobenius norm is equivalent to the problem of finding a low-dimensional subspace that minimizes the sum of squared distances to given points. The general subspace approximation problem asks one to find a low-dimensional subspace that minimizes the sum of p-th powers of distances (for p ≥ 1) to given points. We generalize our sampling techniques and prove similar sampling-based dimension reduction results for subspace approximation. However, the proof is geometric.

Based on joint work with Luis Rademacher, Grant Wang, Santosh Vem- pala, and Kasturi Varadara jan.

The Donaldson invariants for CP² were obtained as the u-plane integral from an N=2 supersymmetric topological U(1)-gauge theory by Moore and Witten. We derive the generating function for the Donaldson invariants of CP² as the stationary phase approximation of the low-energy effective U(1)-gauge theory on CP² thus obtaining an interpretation of the u-plane integral in terms of determinant line bundles. For the product of the determinant line bundles, the local and global anomalies vanish. Moreover, the product has a canonical trivialization.

We show that the u-plane integral also arises as the stationary phase approximation of a topological sigma-model on an elliptic curve at the boundary of the Coulomb branch. The semi-classical partition function is described in terms of determinant line bundles on the Coulomb branch. We show that in terms of the partition function on the elliptic curve, the blow-up function for the Donaldson invariants derived by Fintushel and Stern arises in a natural way.

In the past decade, biology has been revolutionized by an explosion in the availability of data. Translating this new wealth of information into meaningful biological insights and clinical breakthroughs will require a complete overhaul both in the questions being asked, and the methodologies used to answer them. One of the largest challenges in organizing and understanding the data coming from genome sequencing, microarray experiments, and other high-throughput measurements, will be the ability to find large-scale structure in biological systems. Ideally, this would lead to a simplified representation, wherein the thousands of genes in an organism can be viewed as a much smaller number of dynamic modules working in concert to accomplish cellular functions.

Toward demonstrating the importance of higher-level, modular structure in biological systems, we have performed the following analyses:

1. Using computational techniques and pre-existing protein-protein interaction (PPI) data, we have developed general tools to find and validate modular structure. We have applied these approaches to the PPI networks of yeast, fly, worm, and human.
2. Utilizing a modular scaffold, we have generated predictions that attempt to explain existing system-wide experiments as well as predict the function of otherwise uncharacterized proteins.
3. To determine whether modular structure can help explain molecular evolutionary constraints, we have measured the relationship between modularity and evolutionary rate across the proteome.
4. Following the example of comparative genomics, we have aligned biological networks at the modular level to elucidate principles of how modules evolve. We show that conserved modular structure can further aid in functional annotation across the proteome.

In addition to the detection and use of modular structure for computational analyses, experimental techniques must be adapted to support top-down strategies, and the targeting of entire modules with combinations of small-molecules. With this in mind, we have designed experimental strategies to find sets of small-molecules capable of perturbing functional modules through a variety of distinct, but related, mechanisms. As a first test, we have looked for classes of small-molecules targeting growth signaling through the phosphatidyl-inositol-3-kinase (PI3K) pathway. This provides a platform for developing new screening techniques in the setting of biology relevant to diabetes and cancer.

In combination, these investigations provide an extensible computational approach to finding and utilizing modular structure in biological networks, and experimental approaches to bring them toward clinical endpoints.