Professor Andrew Chi-Chih Yao's Research Seminar


Department of Computer Science , City University of Hong Kong
Participant:
Graduate Student: Sun Xiaoming(Tsinghua), Xu Ying(PKU ),Chen Ning(Fudan) Li Yunpeng(HKUST)
Faculty: Deng Xiaotie( CityU), H.F. Ting(HKU)




Oct 3rd, 2002 Monotone Circuit Depth and Communication Complexity
Oct 20th, 2002 Randomized Lower Bound in Sending Message in Specific Radio Networks ps pdf
Oct 22nd, 2002 A nontrivial inequality in the manuscript above ps pdf
Oct 26th, 2002 MAJORITY Circuit and Two Party Communication Game
Oct 26th, 2002 Using XOR gate to build a circuit to calculate MAJORITY function
Oct 27nd,2002 Yao's minmax Lemma for decide lower bound for sending message in some radio networks
I have Quesion here!

Hinted by Prof.Siu-Wing Cheng
Solved About the distribution
Oh, It has been published! Sad and Depressing original paper
Oct 27th, 2002 Randomized Decision Tree v.s. Determinitic Decision Tree
Nov 3rd, 2002 Algorithm in Scorpion Graph
Nov 3rd, 2002 Randomized Decision Tree Complexity of Read-Once Boolean Function
Nov 4th, 2002 Randomized Broadcast's Lower bound in Radio Network pdf
Nov 5th, 2002 Graph Properties and Evasiveness
Nov 16th, 2002 Noisy Gossiping draft
Nov 18th, 2002 Byzantine General Problem manuscript

Open Problems:
Due to Prof. Andrew Chi-Chih Yao
Sept 12th, 2002 Randomized Lower Bound for Parity Function in Multiparty Communication Model. ps
Sept 26th, 2002 Two Parties Communication Game ps
Sept 26th, 2002 INDEX-SUM Problem and Circuit Complexity Solved By Sun Xiaoming recently!
Oct 3rd, 2002 Improve a Deterministic Gossip Algorithm in Radio Networks