Gauge/gravity duality and the interplay of various fractional branes

We consider different types of fractional branes on a Z2 orbifold of the conifold and analyze in detail the corresponding gauge/gravity duality. The gauge theory possesses a rich and varied dynamics, both in the UV and in the IR. We find the dual supergravity solution, which contains both untwisted and twisted 3-form fluxes, related to what are known as deformation and N=2 fractional branes, respectively. We analyze the resulting renormalization group flow from the supergravity perspective, by developing an algorithm to easily extract it. We find hints of a generalization of the familiar cascade of Seiberg dualities due to a nontrivial interplay between the different types of fractional branes. We finally consider the IR behavior in several limits, where the dominant effective dynamics is either confining in a Coulomb phase or runaway, and discuss the resolution of singularities in the dual geometric background. © 2008 The American Physical Society.

A note on spin-s duality

Duality is investigated for higher spin (s ≥ 2), free, massless, bosonic gauge fields. We show how the dual formulations can be derived from a common "parent", first-order action. This goes beyond most of the previous treatments where higher-spin duality was investigated at the level of the equations of motion only. In D = 4 spacetime dimensions, the dual theories turn out to be described by the same Pauli-Fierz (s = 2) or Fronsdal (s ≥ 3) action (as it is the case for spin 1). In the particular s = 2 D = 5 case, the Pauli-Fierz action and the Curtright action are shown to be related through duality. A crucial ingredient of the analysis is given by the first-order, gauge-like, reformulation of higher spin theories due to Vasiliev. © SISSA/ISAS 2003.

Information relaxations and duality in stochastic dynamic programs

We describe a general technique for determining upper bounds on maximal values (or lower bounds on minimal costs) in stochastic dynamic programs. In this approach, we relax the nonanticipativity constraints that require decisions to depend only on the information available at the time a decision is made and impose a "penalty" that punishes violations of nonanticipativity. In applications, the hope is that this relaxed version of the problem will be simpler to solve than the original dynamic program. The upper bounds provided by this dual approach complement lower bounds on values that may be found by simulating with heuristic policies. We describe the theory underlying this dual approach and establish weak duality, strong duality, and complementary slackness results that are analogous to the duality results of linear programming. We also study properties of good penalties. Finally, we demonstrate the use of this dual approach in an adaptive inventory control problem with an unknown and changing demand distribution and in valuing options with stochastic volatilities and interest rates. These are complex problems of significant practical interest that are quite difficult to solve to optimality. In these examples, our dual approach requires relatively little additional computation and leads to tight bounds on the optimal values. © 2010 INFORMS.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Stochastic monotonicity and duality for continuous time Markov chains with general q-Matrix

The key problems in discussing stochastic monotonicity and duality for continuous time Markov chains are to give the criteria for existence and uniqueness and to construct the associated monotone processes in terms of their infinitesimal q -matrices. In their recent paper, Chen and Zhang [6] discussed these problems under the condition that the given q-matrix Q is conservative. The aim of this paper is to generalize their results to a more general case, i.e., the given q-matrix Q is not necessarily conservative. New problems arise 'in removing the conservative assumption. The existence and uniqueness criteria for this general case are given in this paper. Another important problem, the construction of all stochastically monotone Q-processes, is also considered.

Sequentially continuous non-linear fundamental systems of solutions of affine equations in locally convex spaces

According to the Mickael's selection theorem any surjective continuous linear operator from one Fr\'echet space onto another has a continuous (not necessarily linear) right inverse. Using this theorem Herzog and Lemmert proved that if $E$ is a Fr\'echet space and $T:E\to E$ is a continuous linear operator such that the Cauchy problem $\dot x=Tx$, $x(0)=x_0$ is solvable in $[0,1]$ for any $x_0\in E$, then for any $f\in C([0,1],E)$, there exists a continuos map $S:[0,1]\times E\to E$, $(t,x)\mapsto S_tx$ such that for any $x_0\in E$, the function $x(t)=S_tx_0$ is a solution of the Cauchy problem $\dot x(t)=Tx(t)+f(t)$, $x(0)=x_0$ (they call $S$ a fundamental system of solutions of the equation $\dot x=Tx+f$). We prove the same theorem, replacing "continuous" by "sequentially continuous" for locally convex spaces from a class which contains strict inductive limits of Fr\'echet spaces and strong duals of Fr\'echet--Schwarz spaces and is closed with respect to finite products and sequentially closed subspaces. The key-point of the proof is an extension of the theorem on existence of a sequentially continuous right inverse of any surjective sequentially continuous linear operator to some class of non-metrizable locally convex spaces.

Integral completeness of locally convex spaces

A locally convex space X is said to be integrally complete if each continuous mapping f: [0, 1] --> X is Riemann integrable. A criterion for integral completeness is established. Readily verifiable sufficient conditions of integral completeness are proved.

On stratifiable locally convex spaces

In the present paper we prove several results on the stratifiability of locally convex spaces. In particular, we show that a free locally convex sum of an arbitrary set of stratifiable LCS is a stratifiable LCS, and that all locally convex F'-spaces whose bounded subsets are metrizable are stratifiable. Moreover, we prove that a strict inductive limit of metrizable LCS is stratifiable and establish the stratifiability of many important general and specific spaces used in functional analysis. We also construct some examples that clarify the relationship between the stratifiability and other properties.