讨论组:研究生会议
标题:Randomized Communication Complexity of Determinant over Finite Field,A PTAS for
演讲人: 王晨谷,袁文 University
时间: 2011-10-27 12:00-2011-10-27 14:00
地点:FIT 1-222

内容:
==================================================================
Speaker: Chengu Wang
Title: Randomized Communication Complexity of Determinant over Finite Field
==================================================================

Abstract: Alice and Bob hold two n by n matrices x and y, respectively. They want to communicate as less as possible to compute f(x,y)=det(x+y) mod p, for prime p. This problem is a basic problem in linear algebra. Chu and Schnitger gave an Omega(n^2 log p) deterministic lower bound for deciding f(x,y) is 0 or not. Clarkson and Woodruff proved an Omega(n^2) 1-way randomized lower bound for deciding f(x,y) is 0 or not. We proved an Omega(n^2 log p) randomized/quantum lower bound for deciding f(x,y)=a or b for any non-zero a and b, and for deciding f(x,y)=0 or not. In this talk, I will present some ideas of these two results.

Joint work with Xiaoming Sun

==================================================
Speaker: Wen Yuan
Title: A PTAS for Stochastic Knapsack with Correlated Profit
==================================================
Abstract: Knapsack is a well-known NP-hard problem. Stochastic knapsack with random item sizes is at least as hard as its deterministic version. So we expect no more than a PTAS (polynomial-time approximation scheme). The problem is even more interesting when the profit of an item correlates to the realization of item size. In this talk, I will show a PTAS for stochastic knapsack with random item sizes, and correlated profits.



人物介绍: