We derive efficient algorithms for both detecting and representing matchings in lopsided bipartite graphs; such graphs have so many nodes on one side that it is infeasible to represent them in memory or to identify matchings using standard approaches. Detecting and representing matchings in lopsided bipartite graphs is important for allocating and delivering guaranteed-placement display ads, where the corresponding bipartite graph of interest has nodes representing advertisers on one side and nodes representing web-page impressions on the other; real-world instances of such graphs can have billions of impression nodes. We provide theoretical guarantees for our algorithms, and in a real-world advertising application, we demonstrate the feasibility of our detection algorithms.

We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum. We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of $1-\epsilon$ under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase.

Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2. We also obtain a factor $sqrt{2}$ strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty - that of reducing the cost of certain edges and constructing the dual in this altered instance - and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.

Arora, Rao and Vazirani showed that the standard semi-definite programming (SDP) relaxation of the sparsest cut problem with the triangle inequality constraints has an integrality gap of $O(\sqrt{\log n})$. They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture by constructing an $\Omega(\log \log n)$ integrality gap instance. Khot and Vishnoi had earlier disproved the non-uniform version of this Conjecture. A simple ``stretching'' of the integrality gap instance for the sparsest cut problem serves as an $\Omega(\log \log n)$ integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in Charikar et. al. and Feige and Lee, where it was shown that its integrality gap is bounded from above by $O(\sqrt{\log n} \log \log n).$

A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest integer k for which G has a distinguishing k-labeling. In this paper, we apply the principle of inclusion-exclusion and develop recursive formulas to count the number of inequivalent distinguishing k-labelings of a graph. Along the way, we prove that the distinguishing number of a planar graph can be computed in time polynomial in the size of the graph.

Hilbert posed the following problem as the 17th in the list of 23 problems in his famous 1900 lecture: Given a multivariate polynomial that takes only non-negative values over the reals, can it be represented as a sum of squares of rational functions? In 1927, E.~Artin gave an affirmative answer to this question. His result guaranteed the existence of such a finite representation and raised the following important question: What is the {\bf minimum number} of rational functions needed to represent any non-negative $n$-variate, degree $d$ polynomial? In 1967, Pfister proved that any $n$-variate non-negative polynomial over the reals can be written as sum of squares of at most $2^n$ rational functions. In spite of a considerable effort by mathematicians for over 75 years, it is not known whether $n+2$ rational functions are sufficient! In lieu of the lack of progress towards the resolution of this question, we initiate the study of Hilbert's 17th problem from the point of view of Computational Complexity. In this setting, the following question is a natural relaxation: What is the {\bf descriptive complexity} of the sum of squares representation (as rational functions) of a non-negative, $n$-variate, degree $d$ polynomial? We consider arithmetic circuits as a natural representation of rational functions. We are able to show, assuming a standard conjecture in complexity theory, that it is impossible that every non-negative, $n$-variate, degree four polynomial can be represented as a sum of squares of a small (polynomial in $n$) number of rational functions, each of which has a small size arithmetic circuit (over the rationals) computing it.

Our result points to the direction that it is unlikely that every non-negative, $n$-variate polynomial over the reals can be written as a sum of squares of a polynomial (in $n$) number of rational functions. Further, relating to standard (and believed to be hard to prove) complexity-theoretic conjectures sheds some light on why it has been difficult for mathematicians to close the $n+2$ and $2^n$ gap. We hope that our line of work will play an important role in the resolution of this question.