# Stanford CS Theory Lunch

## Logistics

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

Location: Gates 4B lobby.

Mailing list: thseminar@cs.stanford.edu. Email Kshipra to sign up.

Contact: Kshipra Bhawalkar (kshipra@stanford...)

## Spring 2011--2012 Schedule

• (Apr. 5) Faculty Panel

Panelists: Dan Boneh, Don Knuth, Luca Trevisan, Tim Roughgarden,

• (Apr. 12) Don Knuth: Reluctant Doubling

The talk will be about some practical ramifications of a nice paper by Luby, Sinclair, and Zuckerman, Information Processing Letters 47 (1993), 173--180.

• (Apr. 19) Omer Tamuz (Weizmann Institute of Technology): Testing Booleanity and the Uncertainty Principle

Joint work with Tom GurLet f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}.

We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain.

It follows that given black box access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Omega(k) queries lower bound for this problem.

We also consider the problem of deciding if a function is Boolean, given its explicit representation as a k term multilinear polynomial. The naive approach of evaluating it at every input has O(kn2^n) time complexity. For large k (i.e, exponential) we present a simple randomized O(kn sqrt(2^n)) algorithm. For small k we show how the problem can be solved deterministically in O(k^3n).

Our proofs crucially use Hirschman's entropic version of Heisenberg's uncertainty principle.

• (Apr. 26) Zvika Brakeski (Stanford): Efficient Interactive Coding Against Adversarial Noise

We study the problem of constructing interactive protocols that are robust to noise,a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given an interactive protocol which is designed to run on an error-free channel, construct a protocol that evaluates the same function (or, more generally, simulates the execution of the original protocol) over a noisy channel. As in (non-interactive) error correcting codes, the noise can be either stochastic, i.e.\ drawn from some distribution, or adversarial, i.e.\ arbitrary subject only to a global bound on the number of errors.

We show how to \emph{efficiently} simulate any interactive protocol in the presence of constant-rate adversarial noise, while incurring only a constant blow-up in the communication complexity ($\cc$).

Our simulator is randomized, and succeeds in simulating the original protocol with probability at least $1-2^{-\Omega(\cc)}$.

Joint work with Yael Tauman Kalai.

• (May 3) Shailli Jain (Yale): Efficient Crowdsourcing Contests

We present a new model of crowdsourcing, in which a principal seeks production of a single good from a number of potential producers within a limited time frame. There is a hard deadline, after which any good produced has no value to the principal. The output of each producer is a stochastic function of effort expended, which in light of the deadline, may warrant simultaneous production of multiple goods, despite there being no value for extra goods produced. This motivates crowdsourcing as a model of procurement. We address efficient execution of crowdsourcing from a social planner’s perspective, taking into account the value to the principal and the costs to producers (modeled as effort expenditure), while contending with self-interest on the part of all players. A solution to this problem involves an algorithmic aspect that determines an optimal effort level for each producer given the principal’s value, and an incentive mechanism that achieves implementation of the socially optimal policy in equilibrium. In contrast to popular “winner take all” contests, the efficient mechanism we propose involves a payment to every producer that expends non-zero effort in the efficient policy.

Joint work with Ruggiero Cavallo.

• (May 10) David Lee (Stanford): Triadic Consensus: A randomized mechanism for voting in a crowd

Motivated by the hope of developing group consensus mechanisms over the internet, we study an urn-based voting rule where each participant acts as a voter and a candidate. Each participant starts with one ball in an urn. At each step, three balls are selected, a vote takes place between them, and three copies of the winning ball is returned to the urn. We prove that when participants lie in a one-dimensional space, this voting protocol finds a (1-\epsilon/\sqrt{n}) approximation of the Condorcet winner with high probability while only requiring an expected O(1/\epsilon^2 \log^2 (n/\epsilon^2)) comparisons on average per voter. We also show that under certain settings, this voting protocol has a quasi-truthful Nash equilibrium: namely, a Nash equilibrium exists which is not truthful, but produces a winner with the same probability distribution as that of the truthful strategy.

• (May 17) Sachin Katti (Stanford): Strider: Rateless Coding for Wireless Channels

A fundamental problem in wireless networks is to develop communication protocols that achieve high throughput in the face of noise, interference, and time-varying channel conditions. Traditionally, this is done by explicit adaptation, the sender explicitly estimates the channel to the receiver, and picks the right code to encode its message. Such explicit adaptation is expensive and often inaccurate since wireless channels vary continuously.

This talk presents Strider, a rateless wireless system, which solves this problem without any explicit adaptation. In Strider, the sender encodes the data using a novel rateless code, which uses random linear combinations over the message symbols to directly produce a sequence of constellation symbols for transmission. Inspite of no explicit feedback or adaptation, Strider codes nearly achieve Shannon capacity over Gaussian channels, adapt well to changing channel conditions, and can be implemented efficiently. I will provide an intuitive proof sketch, as well as implementation results showing the efficacy of Strider.

• (May 24) Jonathan Ullman (Harvard): Faster Algorithms for Privately Releasing Marginals

We study the problem of releasing k-way marginals of a database D in ({0,1}^d)^n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of D's records x in {0,1}^d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses of a dataset, and designing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf.~Barak et.~al., PODS '07).

We give an algorithm that runs in time d^{O(\sqrt{k})} and releases a private summary capable of answering any k-way marginal query with at most +/- .01 error on every query as long as n >= d^{O(\sqrt{k})}. To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with non-trivial worst-case accuracy guarantees in time substantially smaller than the number of k-way marginal queries, which is d^{\Theta(k)} (for k << d).

Joint work with Justin Thaler and Salil Vadhan

• (May 31) Rishi Gupta (Stanford): A Compressive Sensing Algorithm for Attitude Determination

We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. In the process, we construct a compressive sensing matrix A and corresponding recovery algorithm such that:

(i) if there are k objects, the number of measurements is O((k log N)/(log k)), undercutting the best known bound of O(k log(N/k)), (ii) the matrix A is very sparse, which is important for hardware implementations of compressive sensing algorithms, and (iii) the recovery algorithm is empirically fast and runs in time polynomial in k and log(N).

Joint work with Piotr Indyk, Eric Price, and Yaron Rachlin.

• (6/7) Peter Lofgren (Stanford): Personalized PageRank and Susceptibility

Personalized PageRank uses a random walk distribution to measure the importance of nodes in a directed graph from the point of view of a given node. Susceptibility measures how important a given node is from the point of view of each other node. These measures can be used to place advertising in a social network or to find search results personalized to individual users. In this talk we present an algorithm for computing susceptibility and present preliminary work a sketch based oracle for all-pairs personalized PageRank.

Also check here for the Google calendar.

For previous quarter talks see theory lunch archives.