\documentclass[14pt]{article}

\usepackage{epsf}
\usepackage{epsfig}
\usepackage{color}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}  
\usepackage{amssymb}    
\usepackage{amsthm}
\usepackage{wrapfig}
\usepackage{subfigure}
\usepackage{hyperref}

%\usepackage{fancyheadings}
%\pagestyle{fancy}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}
\widowpenalty 10000

\usepackage{color}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.9}
\newcommand{\aside}[1]{\textcolor{MyDarkBlue}{#1}}

\usepackage{enumerate}


\usepackage{lineno}
%\linenumbers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mybox}[1] {
\begin{center} {\small
\framebox[3in]{
\begin{minipage}[t]{4.5in} {\sf #1}
\end{minipage} } }
\end{center}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength\oddsidemargin{0in}
%\setlength{\textwidth}{6.5in}
\setlength{\textwidth}{4in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\latex{latex }
\newcommand{\header}[1]{\section*{#1}}
\newcommand{\myquote}[1]{''{#1}''}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

{\huge Congratulations, Noam}

{\it The winner of the 2016 ACM-IEEE Knuth Prize}
\vspace{.5in}

Noam Nisan has been one of the leaders in computational complexity and algorithms for many years.  He has just been named the \href{http://www.acm.org/media-center/2016/september/knuth-prize-2016}{winner} of the 2016 Donald E. Knuth Prize. 

Today we congratulate Noam and highlight some of his recent contributions to algorithmic economics and complexity.

%KEN my thoughts
%\begin{quotation}
%I think that Noam missed out on proper recognition is the past. I am thrilled that he is finally recognized for his brilliant work. I do differ with the Knuth citation. His game theory work is clearly important, but his early work on pseudorandom generators was of first order. And personally I wonder if that almost alone would be enough to argue that Noam is one of the great leaders in complexity theory. 
%\end{quotation}

I (Dick) think that Noam missed out on proper recognition in the past. I am thrilled that he is finally recognized for his brilliant work. I do differ with the impression given by ACM's headline. His game theory work is clearly important, but his \href{https://www.amazon.com/Problems-Pseudorandom-Generators-Doctoral-Dissertation/dp/026264052X}{early} \href{https://pdfs.semanticscholar.org/b038/6dce0af09b91f5b24393d294e7066323d44e.pdf}{work} on pseudorandom generators was of first order. And personally I wonder if that almost alone would be enough to argue that Noam is one of the great leaders in complexity theory---let alone the work on communication complexity and interactive proofs. 

I (Ken) had forgotten that he was the 'N' in the LFKN \href{http://dl.acm.org/citation.cfm?id=146605}{paper} with Carsten Lund, Lance Fortnow, and Howard Karloff proving that interactive proofs can simulate the polynomial hierarchy, which presaged the proof of $\mathsf{IP = PSPACE}$.  The first sentence of the ACM article does list these three complexity areas before mentioning game theory.  There are others: Noam co-authored with Nathan Linial and Yishay Mansour a seminal 1993 \href{http://www.ma.huji.ac.il/~ehudf/courses/anal09/LMN.pdf}{paper} that promoted Fourier analysis to study Boolean circuits, and with Mario Szegedy a 1994 \href{https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials}{paper} on the polynomial method that impacted a host of topics including Boolean function sensitivity, decision trees, and quantum query lower bounds.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Walking Out and Back}

In what Lance once \href{http://blog.computationalcomplexity.org/2008/07/one-who-walked-away.html}{termed} ``walking away'' from complexity, Noam in the mid-1990s became interested in algorithmic economics.  
% Noam's first great contributions were on the relationship between pseudorandom generators and complexity lower bounds.  He co-authored with Avi Wigderson the 1988 \href{http://ieeexplore.ieee.org/document/21916/}{paper} whose title articulated the ``Hardness Versus Randomness'' mechanism.  His \href{https://www.amazon.com/Problems-Pseudorandom-Generators-Doctoral-Dissertation/dp/026264052X}{thesis}, which won a 1990 ACM Distinguished Dissertation award, included what are still largely the most efficient and effective pseudorandom generators that are \href{https://pdfs.semanticscholar.org/b038/6dce0af09b91f5b24393d294e7066323d44e.pdf}{impervious} to low space-bounded computations; we have \href{https://rjlipton.wordpress.com/2010/10/31/the-warranty-on-nisans-generator/}{covered} some later work on them.  
Really we should say it is the interface between complexity and economics.  We can say that theory---in particular mathematical game theory---frames much of this interface, but the business end of it is \emph{social}.  The genius we note in his seminal \href{http://dl.acm.org/citation.cfm?doid=301250.301287}{paper} with Amir Ronen, titled ``Algorithm Mechanism Design,'' is in mapping the social elements to structures in distributed computation and communication theory (routing and protocols as well as communication complexity) that were already developed.  This paper was one of three jointly \href{http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012/}{awarded} the 2012 G\"odel Prize.  Regarding it, the Knuth citation says: 

\begin{quotation}
A mechanism is an algorithm or protocol that is explicitly designed so that rational participants, motivated purely by their self-interest, will achieve the designer's goals. This is of paramount importance in the age of the Internet, with many applications from auctions to network routing protocols. Nisan has designed some of the most effective mechanisms by providing the right incentives to the players. He has also shown that in a variety of environments there is a tradeoff between economic efficiency and algorithmic efficiency.
\end{quotation}

% https://rjlipton.wordpress.com/2010/10/31/the-warranty-on-nisans-generator/   OUR post on his earlier work

The last part of this addresses a question of more general import to us in theory:

\begin{quotation}
How much impact can complexity lower bounds and conditional hardness relationships have in the real world?
\end{quotation}

The impact is helped along when the lower bounds come from communication complexity.  Bounds on the number of bits that must be communicated to achieve a common goal (with high probability) are generally more concrete and easier to establish than those in the closed system of classical complexity theory, whose internal nature makes the most central bound questions asymptotic.  

Noam long ago co-authored the \href{https://www.amazon.com/Communication-Complexity-Eyal-Kushilevitz/dp/052102983X}{textbook} \emph{Communication Complexity} with Eyal Kushilevitz, and also co-edited the 2007 \href{https://www.amazon.com/Algorithmic-Game-Theory-Noam-Nisan/dp/0521872820}{text} \emph{Algorithmic Game Theory} with Tim Roughgarden, \'Eva Tardos, and Georgia Tech's own Vijay Vazirani.  The whole package of great breadth as well as depth in foundational areas, imbued with computer science education, ably fits the Knuth Prize profile.  But we are going to make a forward-looking point by exploring how some of his recent joint papers reach a synthesis that includes some implications for complexity. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Four Recent Papers}

$\bullet$ ``Public Projects, Boolean Functions,
and the Borders of Border's Theorem'' \href{https://arxiv.org/pdf/1504.07687v1.pdf}{with} Parikhshit Gopalan and Tim Roughgarden, \href{http://dblp.uni-trier.de/db/conf/sigecom/sigecom2015.html#GopalanNR15}{in} the 2015 ACM Conference on Economics and Computation.  Border's Theorem is an instance where the feasible space of an exponential-sized linear program has a natural projection onto the space of a polynomial-sized one. The linear programs express allocations of $m$-many bid-for goods to $n$ bidders according to their expressed and private valuations of those goods.  The paper shows complexity obstacles to extending this nice exponential-to-polynomial property to other economic situations.

The overall subject can be read about in two sets of \href{http://theory.stanford.edu/~tim/notes.html}{lecture notes} by Roughgarden. We adapt an example from section 2 of this \href{http://theory.stanford.edu/~tim/w14/l/l38.pdf}{lecture} to give the flavor: Suppose you have 2 items for sale and one prospective buyer such that for each item there is a 50-50 chance the buyer is willing to pay \$1 for it, but you lose \$1 for each item you fail to sell (call it shelving cost).  If you price each item at \$1, you will expect to make one sale, reaping \$1 but also losing \$1 on the unsold item, for zero expected net revenue.  That's no better than if you gave each away for \$0.  If you set the price in-between, say \$0.50, you will expect a net loss---because the buyer's probability distribution of value is discrete not smooth.  But if you bundle them at 2-for-\$1, you will expect to sell the bundle three-fourths of the time, for expected net revenue (\$1 + \$1 + \$1 - \$2)/4 = \$0.25, which is positive. 

Our change from Roughgarden's prices and values of \$1,\$2 is meant to convey that problems about (random) Boolean functions and set systems are lurking here.  Suppose we have $n$ items; what is the optimal bundling strategy?  Grouping them at \$2-for-4 expects to net the same \$0.125 per item as the above grouping \$1-for-2.  But grouping \$1-for-3 expects to reap \$1 seven-eights of the time and lose \$3 one-eighth of the time, for \$4/8 = \$0.50 net for 3 items, which gives a slightly better \$0.167 per item.  Is this optimal?  We could write a big linear program to tell---also in situations with other prices and distributions of buyer values and conditions.  

In many of these situations, they show that a Border-like theorem would put a $\mathsf{\#P}$-hard problem into $\mathsf{P^{NP}}$ and hence collapse the polynomial hierarchy.  A key technical tool is the expectation $\hat{f}_0$ of a Boolean function $f$ over a random assignment and for each $i$ the expectation $\hat{f}_i$ of $(-1)^{1 - x_i}f(x)$, which constitute the zeroth and first-degree coefficients of the Fourier transform of $f$.  Certain $\mathsf{\#P}$-hard problems about vectors of these coefficients are mapped into economics problems for which smaller LPs would collapse them.

\bigskip
$\bullet$   ``Networks of Complements'' \href{http://drops.dagstuhl.de/opus/volltexte/2016/6284/pdf/LIPIcs-ICALP-2016-140.pdf}{with} Moshe Babaioff and Liad Blumrosen, \href{http://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#BabaioffBN16}{in} ICALP 2016.  Imagine a situation where buyers will only buy pairs of items in bundles.  We can make an undirected graph whose nodes are the items and each edges is weighted by the price the buyer is willing to pay.  Graph theory supplies tools to analyze the resulting markets, while behavior for special kinds of graphs may yield insights about the structure of problems involving them.

\bigskip
$\bullet$ ``A Stable Marriage Requires Communication,'' \href{http://epubs.siam.org/doi/pdf/10.1137/1.9781611973730.68}{with} Yannai Gonczarowski, Rafail Ostrovsky, and Will Rosenbaum, \href{http://dblp.uni-trier.de/db/conf/soda/soda2015.html#GonczarowskiNOR15}{in} SODA 2015.  The input consists of $2n$ permutations $m_1,\dots,m_n$ and $w_1,\dots,w_n$ of $[n]$.  A bijection $\mu: [n] \to [n]$ is \emph{unstable} if there exist $i,j \in [n]$ such that $m_i(j) > m_i(\mu(i))$ and $w_j(i) > w_j(\mu^{-1}(j))$.  Figuratively, the latter means that woman $j$ prefers man $i$ to her own husband and the former means that man $i$ likewise prefers woman $j$ to his own wife.  There always exist ``marriage functions'' $\mu$ that are stable, but the problem is to find one.

This is a classic example of a problem whose best-known algorithms run in time order-of $n^2$ in worst case, but $O(n\log n)$ time in average case for permutations generated uniformly at random.  This random model may not reflect ``practical case'' however, so the worst-case time merits scrutiny for possible improvement, perhaps under some helpful conditions.  One avenue of improvement is not to require reading the whole input, whose size when the permutations are listed out is already order-of $n^2$ (ignoring a log factor by treating elements of $[n]$ as unit size), but rather allow random access to selected bits.  These queries can be comparisons $w_i(j) > w_k(\ell)$ or more general.  The paper finds a powerful new reduction from the communication complexity of disjointness (if Alice and Bob each hold an $n$-bit binary string, verify there is no index $i$ where each string has a $1$) to prove the query number must be $\Omega(n^2)$ even for randomized algorithms and even with certain extra helpful conditions.  


\bigskip
$\bullet$ ``Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions,'' \href{http://dl.acm.org/citation.cfm?id=2840738}{with} Parikhshit, Rocco Servedio, Kunal Talwar, and Avi, \href{http://dblp.uni-trier.de/db/conf/innovations/innovations2016.html#GopalanNSTW16}{in} the 2016 Innovations conference.  

The \emph{sensitivity} $s(f)$ of (a family of) $n$-variable Boolean functions $f$ is the minimum over $x$ of the number of $y$ adjacent to $x$ such that $f(y) \neq f(x)$.  Here adjacent means $x$ and $y$ differ in one bit.  The functions are \emph{smooth} if $s(f) = (\log n)^{O(1)}$, or variously, if $s(f) = n^{o(1)}$.   One way to achieve $s(f) \leq d$ is for $f$ to be computed by a depth-$d$ decision tree, since along each branch determined by an $x$ there are at most $d$ bits on which the branch's assigned value depends.  Noam, first solo and then in the 1994 paper with Szegedy, conjectured a kind of converse: there is a universal constant $c$ such that every $f$ has a decision tree of size $s(f)^c$.  

Decision trees are broadly more powerful in corresponding depth and size measures than Boolean circuits, which in turn are more powerful than formulas.  Although belief in Noam's conjecture has grown, no one had determined upper bounds for circuits and formulas.  The paper gives circuits of size $O(n^{s(f)})$ and formulas of depth $O(s(f)\log n)$ with somewhat laxer size $n^{O(s(f))}$.  The size is scarcely the same as a polynomial in $s(f)$, but it's a start, and when $s(f)$ is polylog, the size is quasipolynomial and the depth is polylog.  This most-recent paper will hopefully jump-start work on proving the conjecture and fundamental work on Boolean functions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Open Problems}

We congratulate Noam warmly on the prize and his research achievements.  

We can announce one new thing: \href{https://itunes.apple.com/us/podcast/lemonades-podcast/id1161181689}{LEMONADE}.  No it is not Beyonc\'e's new album but rather Richard and Kathryn's new podcast series on positive approaches to problematic issues in academia, culture, and life in general.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


