# Stanford CS Theory Lunch

## Logistics

Time: Thursdays, typically 12:30pm to 1:00pm (food starts at 12:15pm)

Location: Gates 4B lobby.

Contact: Kevin Lewi (klewi at cs dot stanford dot edu)

## Winter 2012--2013 Schedule

• (1/10) Don Knuth (Stanford): Nice Proofs About Tree Resolution
• (1/17) Anindya De (Berkeley): Inverse problems in approximate uniform generation.

We initiate the study of "inverse" problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function$f$ belonging to a class $C$ of Boolean functions (such as linear threshold functions or polynomial-size DNF formulas), and the goal is to output a probability distribution $D$ which is $\epsilon$-close, in total variation distance, to the uniform distribution over $f^{-1}(1)$. Problems of this sort comprise anatural type of unsupervised learning problem in which theunknown distribution to be learned is the uniform distribution over satisfying assignments of an unknown function $f \in C.$

We prove a general positive result establishing sufficient conditions for efficient inverseapproximate uniform generation for a class $C$ based a new type of algorithm called a "densifier" for $\C$. We apply this general result to obtain a poly$(n,1/\eps)$-timeinverse approximate uniform generation algorithm for the class of $n$-variable linear threshold functions (halfspaces); and a quasipoly$(n,1/\eps)$-time inverseapproximate uniform generation algorithm for the class of $\poly(n)$-size DNF formulas.

Based on well-known cryptographic assumptions, we show that there are no subexponential-time inverse approximate uniform generation algorithms for 3-CNF formulas; for intersections of two halfspaces; for degree-2 polynomial threshold functions; and for monotone 2-CNF formulas. Our negative results can also be seen to be related to the seminal result of Jerrum, Valiant and Vazirani on uniform sampling of witnesses for NP-complete sets.

Joint work with Ilias Diakonikolas and Rocco Servedio.

• (1/24) Josh Wang (Stanford): Space-Efficient Las Vegas Algorithms for K-SUM

The K-SUM problem is as follows: given a set of numbers, are there K which sum to zero? The complexity of this fundamental problem is related to the complexity of a variety of problems from computational geometry as well as the complexity of NP-complete problems SUBSET-SUM and 3-SAT. Using hashing techniques, I develop a family of space-efficient Las Vegas algorithms for K-SUM, including an algorithm for 3-SUM that runs in O(n^2) expected time and O(n^0.5) space. This family also establishes a new time-space upper bound for SUBSET-SUM.

This research was advised by Ryan Williams.

• (1/31) Kshipra Bhawalkar (Stanford) Co-evolutionary Opinion Formation Games

We present game-theoretic models of opinion formation in social networks where opinions themselves co-evolve with friendships. In these models, nodes form their opinions by maximizing agreements with friends weighted by the strength of the relationships, which in turn depend on difference in opinion with the respective friends. We define a social cost of this process by generalizing recent work of Bindel et al., FOCS 2011. We tightly bound the price of anarchy of the re- sulting dynamics via local smoothness arguments, and char- acterize it as a function of how much nodes value their own (intrinsic) opinion, as well as how strongly they weigh links to friends with whom they agree more.

Joint work with Sreenivas Gollapudi and Kamesh Munagala.

• (2/7) Pranav Dandekar (Stanford): The Dynamics of Polarization in Society

Are we getting more polarized as a society? We will address this question through a model of opinion dynamics similar to the one described by Kshipra last week. Empirical studies have shown that homophily, i.e., greater interaction between like-minded individuals, results in polarization. However, we show that DeGroot's well-known model of opinion formation based on repeated averaging can never be polarizing, even if individuals are arbitrarily homophilous. We generalize DeGroot's model to account for a phenomenon well-known in social psychology as \textit{biased assimilation}: when presented with mixed or inconclusive evidence on a complex issue, individuals draw undue support for their initial position thereby arriving at a more extreme opinion. We show that in a simple model of homophilous networks, our biased opinion formation process results in polarization if individuals are sufficiently biased. In other words, homophily alone, without biased assimilation, is not sufficient to polarize society.

Quite interestingly, biased assimilation also provides a framework to analyze the polarizing effect of Internet-based recommender systems that show us personalized content. In particular, we will show that Personalized PageRank is always polarizing whereas item-based collaborative filtering (think Amazon's recommendations) is polarizing only when users are biased.

Based on joint work with Ashish Goel and David Lee

• (2/14) Huacheng Yu (Stanford): A New Variation of Hat Guessing Games

Several variations of hat guessing games have been popularly discussed in recreational mathematics. In a typical hat guessing game, after initially coordinating a strategy, each of n players is assigned a hat from a given color set. Simultaneously, each player tries to guess the color of his/her own hat by looking at colors of hats worn by other players. In this paper, we consider a new variation of this game, in which we require at least k correct guesses and no wrong guess for the players to win the game, but they can choose to “pass”.

A strategy is called perfect if it can achieve the simple upper bound n/(n+k) of the winning probability. We present sufficient and necessary condition on the parameters n and k for the existence of perfect strategy in the hat guessing games. In fact for any fixed parameter k, the existence of a perfect strategy for (n,k) is open for only a few values of n.

In our construction we introduce a new notion: (d1,d2)-regular partition of the boolean hypercube, which is worth to study in its own right. For example, it is related to the k-dominating set of the hypercube. It also might be interesting in coding theory. The existence of (d1,d2)-regular partition is explored in the paper and the existence of perfect k-dominating set follows as a corollary.

• (2/21) Shayan Oveis Gharan (Stanford): Improved Cheeger's Inequality: Analysis of Spectral Partitioning through Higher Order Spectral Gap

Cheeger's influential inequality in spectral graph theory [Alon,Milman'85] relates the second smallest eigenvalue of the normalized laplacian matrix to the sparsity of the sparsest cut of a graph. This inequality provides a simple linear time approximation algorithm, a.k.a. spectral partitioning algorithm, for the sparsest cut problem.

We improve Cheeger's inequality using higher order eigenvalues. This implies an improved guarantee on the performance of the spectral partitioning algorithms. Our proof provides a rigorous justification to the empirical performance of spectral partitioning algorithm in image segmentation and clustering problems.

Based on a joint work with Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee and Luca Trevisan.

• (2/28) Inbal Talgam Cohen (Stanford): Refine Predictions Ad Infinitum?

We study how standard auction objectives in sponsored search markets change with refinements in the prediction of the relevance (click-through rates) of ads. We study mechanisms that optimize for a convex combination of efficiency and revenue. We show that the objective function of such a mechanism can only improve with refined (improved) relevance predictions, i.e., the search engine has no disincentive to perform these refinements. More interestingly, we show that under assumptions, refinements to relevance predictions can only improve the efficiency of any such mechanism. Our main technical contribution is to study how relevance refinements affect the similarity between ranking by virtual-value (revenue ranking) and ranking by value (efficiency ranking). Time allowing I will mention implications of our results to the literature on signaling. Joint work with Mukund Sundararajan.

• (3/7) Amir Abboud (Stanford): Exact Weight Subgraphs and the k-Sum Conjecture

We consider the Exact-Weight-H problem of finding a (not necessarily induced) subgraph H of weight 0 in an edge-weighted graph G. We show that for every H, the complexity of this problem is strongly related to that of the infamous k-Sum problem. In particular, we show that under the k-Sum Conjecture, we can achieve tight upper and lower bounds for the Exact-Weight-H problem for various subgraphs H such as matching, star, path, and cycle.

One interesting consequence is that improving on the O(n^3) upper bound for Exact-Weight-4-Path or Exact-Weight-5-Path will imply improved algorithms for 3-Sum, 5-Sum, All-Pairs Shortest Paths and other fundamental problems. This is in sharp contrast to the minimum-weight and (unweighted) detection versions, which can be solved easily in time O(n^2). We also show that a faster algorithm for any of the following three problems would yield faster algorithms for the others: 3-Sum, Exact-Weight-3-Matching, and Exact-Weight-3-Star.

Joint work with Kevin Lewi and advised by Ryan Williams.

• (3/14) Virginia Vassilevska Williams (Stanford): Approximating the diameter of a sparse graph

I'll show how to 3/2-approximate the diameter of an n-node m-edge graph in ~m sqrt n time. I'll also give a simple reduction that shows that improving on the 3/2 approximation factor while still taking n^{2-\eps} time in sparse graphs may be hard as it would imply an improved algorithm for CNF-SAT.

Also check here for the Google calendar.

For previous quarter talks see theory lunch archives.