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.