Professor Andrew Chi-Chih Yao's Research Seminar
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