Group:Theory Lunch
Title: Learning DNF Formula, Quantum Communication Complexity Lower Bound of Inner Prod
Speaker: Chenggu Wang, Wei Hu University
Time: 2010-11-11 12:00-2010-11-11 13:30
Venue: FIT 1-222


Title: Learning DNF formulae


Abstract: In this talk I will show results of learning two special DNF functions[KLW 10]. (1) For a randomly and independently choosen DNF function with t terms and each term is at most \logt, it can be approximated with t^O{\log{1/\epsilon}}-sparse function.(2)  For read-k DNF function, it can be approximated with t^O{16^k\log{1/\spsilon}}-

sparse function.

Title:Quantum Communication Complexity Lower Bound of Inner Product in Finite Field


Abstract: Inner product in Boolean field, IP_2(x,y)=\sum_i x_iy_i mod 2, is a classical function in communication complexity. A generalisation is to consider inner product in finite field F_p. Formally, Alice holds x\in F_p^n, Bob holds y\in F_p^n, and they want to compute IP_p(x,y)=\sum_i x_iy_i in F_p. It is trivial that the deterministic communication complexity of IP_p is O(n log p). It is known that Q^∗(IP_2)=Omega(n) [KremerNisan95], and D(IP_p)=Omega(n log p) [ChuSchnitger95]. We prove that Q^∗(IP_2)=Omega(n log p). In the talk, I will prove the result by the general discrepancy method and show some other related problems.

Short Bio: