[CSDM] [pvsnp-all] CCI Meeting Friday October 5th

[Ankur Moitra]

Hi All,

Here is the schedule for the CCI Meeting next week.

Best, Ankur

CCI Meeting Friday October 5th

10:00-11:00: PI meeting
11:00-12:00: Amir Shpilka
12:00-12:15: Break to get lunch
12:15-1:00: Amir Shpilka continues
2:00-2:30: Jing Chen
2:30-3:00: Andy Drucker
3:00-3:30: Gillat Kol

  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: Epistemic Implementation: 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: TBA

  Speaker: Andy Drucker

  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.

_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all