May 22, 2013

Posts Comments

You are here: Home / Events / Center Meeting: Matrix Multiplication and More Postdoc Talks – October 5, 2012

Center Meeting: Matrix Multiplication and More Postdoc Talks – October 5, 2012

October 2, 2012 By

The October CCI monthly meeting will be Friday October 5th in room 105.  We are excited to have Amir Shpilka and more new center postdocs talking about their recent research.   

10:00-11:00         PI meeting (room 401)

11:00-12:00         On Sunflowers and Matrix Multiplication — Amir Shpilka [Video]

12:00-12:45         lunch

12:45-1:30           On Sunflowers and Matrix Multiplication — Amir Shpilka (continued) [Video]

1:30-2:00             break

2:00-2:30             Mechanisms Leveraging Arbitrary Set-Theoretic Belief Hierarchies — Jing Chen [Video]

2:30-3:00             Constant-depth Circuits with Smooth Probabilistic Gates — Andy Drucker [Video]

3:00-3:30             Covering CSPs — Gillat Kol [Video]

————————————————————————–

Title: On Sunflowers and Matrix Multiplication

Speaker: Amir Shpilka
 
Abstract: We present several variants of the sunflower conjecture of Erdos and Rado and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and of Cohn et al regarding possible approaches for obtaining fast matrix multiplication algorithms. Specifically, we show that the Erdos-Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets'' question of Coppersmith and Winograd; we also formulate a “multicolored'' sunflower conjecture in Z_3^n and show that (if true) it implies a negative answer to the “strong USP'' conjecture of Cohn et al (although it does not seem to impact their second conjecture or the viability of the general group-theoretic approach).
 
Joint work with Noga Alon and Chris Umans.

————————————————————————–

Title: Mechanisms Leveraging Arbitrary Set-Theoretic Belief Hierarchies

Speaker: Jing Chen
 
Abstract: In settings of incomplete information, we model the hierarchy of the players' beliefs about each other?s payoff types in a set-theoretic way, and leverage it to generate revenue in single-good auctions. Our mechanisms have no clue about the players' valuations or beliefs. Yet, they work even when a player's beliefs are totally arbitrary and wrong, the beliefs of different players are inconsistent with each other, and the players are not expected-utility maximizers.
 
For each k greater than or equal to 0, we define a revenue benchmark $G^k$ over the players' order-k beliefs. Our benchmarks are very demanding: they are monotonically non-decreasing in k; $G^0$ is the second highest true valuation; and the gap between each pair $G^k$ and $G^{k+1}$ can be arbitrary. In particular, for each k greater than 0, $G^k$ can be arbitrarily larger than the highest true valuation when the players' beliefs are wrong, and can coincide with the highest true valuation when all beliefs are correct.
 
We construct a single, interim individually rational (IIR) mechanism guaranteeing revenue greater than or equal to $G^k – \epsilon$ for all k and all profiles of order-(k+1) rationalizable actions, where the underlying notion of rationality is the very weak one proposed by Aumann (1995).
 
Finally, we separate the revenue achievable from order-k and order-(k+1) rationalizable actions. Indeed we prove that, for any c>0, no IIR mechanism can guarantee revenue greater than or equal to $G^k – c$ when the played actions are at most order-k rationalizable.

————————————————————————–

Title: Constant-depth Circuits with Smooth Probabilistic Gates

Speaker: Andy Drucker
 
Abstract: I will discuss questions about the power of circuit gates whose probability of outputting 1 is a "smooth" (Lipschitz) function of their input vector. This is an abstraction of neurons with "coarse-threshold" behavior.

————————————————————————–

Title: Covering CSPs
 
Speaker: Gillat Kol
 
Abstract: We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. 
 
This covering notion describes situations in which we must satisfy all the constraints, and are willing to use more than one assignment to do so (as opposed to max-CSP, where we restrict ourselves to a single assignment). At the same time, we want to minimize the number of assignments.
 
We study the covering problem for different constraint predicates, and give a partial characterization of covering-hard predicates. 
 
Joint work with Irit Dinur.
 
Filed Under: Events, Meetings, Talks, Videos