Fridays, 3:30pm, 373 Soda, unless otherwise specified.
January 23, Alexandra Kolla
Merging techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming
Abstract : The talk focuses on expander graphs in conjunction with the combined use of SDPs and eigenvalue techniques for approximating optimal solutions to combinatorial optimization problems. In the first part of the talk I will explain how to construct cost-effective, expanding networks by using "local" sparsifiers of graphs that emerge as a solution to a semidefinite program. In the second part of the talk I will show that the Unique Games Conjecture is false when the underlying constraint graph is a (spectral) expander. Namely, I will present a polynomial-time algorithm for Unique Games on expanding instances that finds a good assignment when there exists one.
January 30, Anupam Prakash
Braverman's Proof of the Linial-Nisan conjecture
Abstract: I will talk about Braverman's recent proof of the Linial-Nisan conjecture. The result says that a polynomial sized constant depth boolean circuit (an AC_0 circuit) can not distinguish between a polylog-wise independent distribution and the uniform distribution with a non negligible probability of success. Inspite of being open for about two decades, the proof is beautiful and short enough to be presented at TGIF. Time permitting we might look at related problems.
February 6, Gregory Valiant
Size (and Treewidth) Bounds for Conjunctive Queries
abstract: given a conjunctive query, a fundamental question is the following: given an input database with N tuples, how large can the result of the query be? In other words, can one extract tight upper bounds on the potential size increase by considering the structural properties of the query itself? (similarly, how much can the query inflate the treewidth of the database? database people care about treewidth, because some queries become NP-hard if the treewidth is large, but are tractable for small treewidth). Unsurprsingly, the answer is 'yes, there are nice bounds'. Surprisingly, this was only addressed in the past two years. I'll present some of this work (part of which is joint work with G. Gottlob and S. Lee), which involves some nice theory tools and combinatorics, and will end with an open problem that I'd be happy to work on with any of you. I hope to see you all at TGIF, -g
Influence in Social Networks
Abstract: I'll talk about the problem computing influential nodes in a social network. I'll cover some of the various models for how nodes influence one another and the known hardness and approximation results.
An Impossibility Theorem for Clustering by Jon Kleinberg
Abstract: This paper presents three natural and reasonable axioms for clustering criteria and shows that they are internally inconsistent. I will cover the proof and then open up the floor for discussion about alternate axioms, axioms for graph clustering and how we can think about community discovery in social networks.
February 27, Grant Schoenebeck
Query Incentive Networks
Abstract:
We will continue our romp through the social networking literature. The over arching theme will be local-global relationships in social networks (very generally).
I will briefly talk about "The Strength of Weak Ties" by Mark Granovetter, which is a classic sociology paper from the 1970's and one of the first to talk about social networking. It has some really cool points in it that I will try to bring up.
The main part of the discussion will be "Query Incentive Networks" by Jon Kleinberg and Prabhakar Raghavan which appeared in FOCS 2005. It talks about a highly stylized model of looking for information in a network setting. The main result is a critical point for branching parameter 2 (you would expect it to be at one). They also show that a NE equilibrium for their game exists.
This paper presents three natural and reasonable axioms for clustering criteria and shows that they are internally inconsistent. I will cover the proof and then open up the floor for discussion about alternate axioms, axioms for graph clustering and how we can think about community discovery in social networks.
Goldreich's Candidate One-Way Function
Abstract:
Goldreich (ECCC 2000) proposed a candidate one-way function construction which is parameterized by the choice of a small predicate (over $d=O(1)$ variables) and of a bipartite expanding graph of right-degree $d$. The function is computed by labeling the $n$ vertices on the left with the bits of the input, labeling each of the $n$ vertices on the right with the value of the predicate applied to the neighbors, and outputting the $n$-bit string of labels of the vertices on the right.
Results by Alekhnovich, Hirsch and Itsykson imply that Goldreich's function is secure against ``myopic'' backtracking algorithms if the 3-ary parity predicate $P(x_1,x_2,x_3) = x_1 \oplus x_2 \oplus x_3$ is used. One must, however, use non-linear predicates in the construction, which otherwise succumbs to a trivial attack via Gaussian elimination.
We generalized the work of Alekhnovich et al. to handle a more general class of predicates, and we present a lower bound for the construction that uses the predicate \( P_d (x_1,\ldots,x_d) := x_1 \oplus x_2 \oplus \cdots \oplus x_{d-2} \oplus (x_{d-1} \wedge x_d) \) and a random graph.
Quantum Query Lower Bounds
Abstract:
I will talk on quantum query lower bounds using the quantum adversary argument developed by Ambainis. I will describe the technique and some of the improved lower bounds that came out of it.
Structure and Randomness in Combinatorics
Abstract:
I will discuss a general paradigm which says that in many settings, an arbitrarily complex object can be decomposed into a "structured" (or low-complexity) part plus a "pseudorandom" part. I will prove one such decomposition theorem, and then show how Szemeredi's regularity lemma follows from it.
The Lovats-Simonovits Theorem
Abstract:
I will talk about the Lovats-Simonovits Theorem. This is a way of reasoning about how low conductance cuts affect the convergence of random walks in graphs, without recurring to spectral techniques. I will present its proof, describe how this theorem is a key component of recent local graph partitioning algorithms and mention some open problems.
Lower Bounds on Metric Embeddings
Abstract:
I will talk about a basic method of proving metric embedding lower bounds and illustrate a couple of textbook examples. Depending on how much time we have after that, I will do one or two more recent ones for earthmover metric and edit distance.
Random Geometric Graphs
Abstract:
I'll give my practice qual talk on a model for mobile wireless networks based on random geometric graph. I will present our results and some open problems that we plan to solve sometime. I will also point out other interesting problems related to random geometric graphs and, time permitting, will briefly comment on my work on different topics.
October 31, Madhur Tulsiani on Lasserre gaps for k-CSPs
Abstract: The Lasserre hierarchy is a way of generating strong semidefinite programs and essentially generated the strongest SDPs we know. Grant recently showed a result which shows that for a binary constraint satisfaction problem (k-XOR), the integrality gap even after lots rounds in the hierarchy is at most 1/2 - \epsilon. This is a strong result, considering that an approximation ratio of 1/2 is trivial: in a random 3-XOR formula only about the 1/2 the clauses can be satisfied and the worst an SDP can do is say that all of them are satisfiable, in which case the gap will be 1/2. I will show an extension of his result, which says that for a general CSP over k variables, the gap is at most k/2^k after lots of rounds. This is the worst one can do for a CSP over k variables since there is an SDP algorithm which approximates them within this factor. If there is time, I'll talk about how to extend these results to CSPs where variables can take values over larger domains (not just binary) and implications for random predicates. Don't worry if you do not understand some words in this abstract: I'll explain them all.
November 14th, Anupam Prakash on Pseudorandom function families, natural proofs and the impossibility of obfuscating circuits
Abstract: We will have a look at the GGM construction of a pseudorandom function family and then see how the argument yields the impossibility of obtaining circuit lower bounds through 'natural proofs'. We will then see why black box circuit obfuscation is impossible i.e. we will construct a function for which the description of any circuit computing the function yields 'more' information than black box access to the function. Time permitting, we might look at other notions of obfuscation.
November 21st, Thomas Watson on Kakeya Sets
Abstract: I will discuss the recent resolution of the Kakeya problem for finite fields. This problem is so simple I can state it right here: A subset K of F^n (where F is a finite field) is called a "Kakeya set" if it contains a line in every direction, in other words, for all Z in F^n there exists an X in F^n such that for all y in F, X+yZ is in K. It was conjectured that every Kakeya set has size at least c_n * |F^n| where the value of c_n depends only on n. This conjecture was recently proved via a remarkably simple proof, which I will present. The connection to computer science is that Kakeya sets crop up in the analysis of certain pseudorandom objects called mergers; I will also discuss this connection.
December 5th, Yaron Singer on Reverse Mechanisms on a Budget
Abstract: In almost all real world settings participants in an auction are limited
by a budget. Surprisingly, this is almost virgin territory in mechanism
design. We discuss a new setting in which we wish to design incentive
compatible algorithms for buying items from strategic agents. Instead
of algorithms which deal with the true reported costs, our algorithms
must "bribe" the agents to elicit truthfulness, efficiently, under the
budget. We show a general class of mechanisms that gives constant
factor incentive compatible approximations for various interesting
settings. For a more complex setting, however, we show a negative
result. While designing incentive compatible algorithms in this setting
is trivial when payments are unrestricted, we show that our mechanisms,
along with a very rich class of "reasonable" mechanisms, cannot obtain
good approximations, due to the budget limitations.
This is joint work with Arpita Ghosh and Amin Saberi.