Georgia Institute of Technology College of Sciences

In 1997 Kannan and Frieze defined the \emph{cut-norm} $\left\Vert A\right\Vert_{\square}$ of a $p\times q$ matrix $A=\left[ a_{ij}\right] $ as%\[\left\Vert A\right\Vert _{\square}=\frac{1}{pq}\max\left\{ \left\vert\sum_{i\in X}\sum_{j\in Y}a_{ij}\right\vert :X\subset\left[ p\right],Y\subset\left[ q\right] ,\text{ }X,Y\neq\varnothing\right\} .\]More recently, Lov\'{a}sz and his collaborators used the norm $\left\VertA\right\Vert _{\square}$ to define a useful measure of similarity between anytwo graphs, which they called \emph{cut-distance. }It turns out that the cut-distance can be extended to arbitrary complexmatrices, even non-square ones. This talk will introduce the basics of thecut-norm and \ cut-distance for arbitrary matrices, and present relationsbetween these functions and some fundamental matricial norms, like theoperator norm. In particular, these relations give a solution to a problem of Lov\'{a}sz.Similar questions are discussed about the related norm\[\left\Vert A\right\Vert _{\boxdot}=\max\left\{ \frac{1}{\sqrt{\left\vertX\right\vert \left\vert Y\right\vert }}\left\vert \sum_{i\in X}\sum_{j\inY}a_{ij}\right\vert :X\subset\left[ p\right] ,Y\subset\left[ q\right],\text{ }X,Y\neq\varnothing\right\} .\]which plays a central role in the \textquotedblleft expander mixinglemma\textquotedblright.

Abstract: A hitting set for a collection of sets T is a set that has a non-empty intersection with eachset in T; the hitting set problem is to find a hitting set of minimum cardinality. Motivated bythe fact that there are instances of the hitting set problem where the number of subsets to behit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting setproblem the collection of sets to be hit is typically too large to list explicitly; instead, an oracleis provided which, given a set H, either determines that H is a hitting set or returns a set inT that H does not hit. I will show a number of examples of classic implicit hitting set problems,and give a generic algorithm for solving such problems exactly in an online model.I will also show how this framework is valuable in developing approximation algorithms by presenting a simple on-line algorithm for the minimum feedback vertex set problem. In particular, our algorithm gives an approximation factor of 1+ 2 log(np)/(np) for the random graph G_{n,p}.Joint work with Richard Karp, Erick Moreno-Centeno (UC, Berkeley) and Santosh Vempala (Georgia Tech).

A starting point of geometric group theory is thinking of a group as a geometric object, by giving it a metric induced from the Cayley graph of the group. Gromov initiated a program of studying groups up to quasi-isometries, which are ``bilipschitz maps up to bounded additive error". Quasi-isometries ignore local structure and preserve asymptotic properties of a metric space. In the talk I will give a sample of results, examples, and open questions in this area.

We improve the lower bound for the L_\infty norm of the discrepancy function. This result makes a partial step towards resolving the Discrepancy Conjecture. Being a theorem in the theory of irregularities of distributions, it also relates to corresponding results in approximation theory (namely, the Kolmogorov entropy of spaces of functions with bounded mixed derivatives) and in probability theory (namely, Small Ball Inequality - small deviation inequality for the Brownian sheet). We also provide sharp bounds for the exponential Orlicz norm and the BMO norm of the discrepancy function in two dimensions. In the second part of the thesis we prove that any sufficiently smooth one-dimensional Calderon-Zygmund convolution operator can be recovered through averaging of Haar shift operators. This allows to generalize the estimates, which had been previously known for Haar shift operators, to Calderon-Zygmund operators. As a result, the A_2 conjecture is settled for this particular type of Calederon-Zygmund operators.