Georgia Institute of Technology College of Sciences

I will talk about new results on convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. In particular: (i) show a new convex program for the linear utilities case of Fisher markets. This program easily extends to the case of spending constraint utilities as well, thus resolving an open question raised by Vazirani; (ii) show that the gradient descent algorithm with respect to a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate); (iii) show that the Proportional Response dynamics recently introduced by Zhang is equivalent to a gradient descent algorithm for solving the new convex program. This insight also gives us better convergence rates, and helps us generalize it to spending constraint utilities.

In the talk we will consider the problem of deciding whether agiven $r$-uniform hypergraph $H$ with minimum vertex degree atleast $c|V(H)|$, has a vertex 2-coloring. This problem has beenknown also as the Property B of a hypergraph. Motivated by an oldresult of Edwards for graphs, we summarize what can be deducedfrom his method about the complexity of the problem for densehypergraphs. We obtain the optimal dichotomy results for2-colorings of $r$-uniform hypergraphs when $r=3,4,$ and 5. During the talk we will present the NP-completeness results followed bypolynomial time algorithms for the problems above the thresholdvalue. The coloring algorithms rely on the known Tur\'{a}n numbersfor graphs and hypergraphs and the hypergraph removal lemma.

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.