CMSC 752, FALL 2008 HOMEPAGE

Here is our syll.ps, syll.pdf

HANDOUTS

JUST FOR FUN

CMSC 752 DRINKING GAME DRINKINGGAME.PDF, DRINKINGGAME.PS,

PURE COMMUNICATION COMPLEXITY:

AVG CASE COMPLEXITY of EQUALITY: EQ.PDF, EQ.PS

BRANCHING PROGRAMS:

MULTI-COMM COMP I- CONN TO RAMSEY THEORY MULTICOMMCONN.PDF, MULTICOMMCONN.PS,

MULTI-COMM COMP II- RAMSEY THEORY MULTICOMMRAMSEY.PDF, MULTICOMMRAMSEY.PS,

MULT-COMM COMP III- APPS TO BP's MULTICOMMBP.PDF, MULTICOMMBP.PS,

ORIG PAPER ON MULTIPARTY MULTIPARTYPROTOCOLS.PDF, MULTIPARTYPROTOCOLS.PS

APPS OF COMM COMP TO BP. BP.PDF, BP.PS

PAPER Bounded-Width Poly-Size Branching Programs Recognize those languages in $NC^1$ by Barrington. BP5.PDF, BP5.PS,

CELL PROBE BIT COMPLEXITY:

NOTES ON BPDS CELLMEMBIT.PDF, CELLMEMBIT.PS,

NOTES ON BPDS-EASY STUFF: CELLEASY.PDF, CELLEASY.PS,

NOTES ON BPDS-FOUR PROBES: CELLFOUR.PDF, CELLFOUR.PS,

SAMPLE PROBLEMS ON BPDS SAMPLE.PDF, SAMPLE.PS,

MATTS SUMMARY OF RESULTS CELLSUMMARY.PDF, CELLSUMMARY.PS,

PAPER On the Power of Two, Three, or Four Probes by Alon and Feige 234PROBES.PDF,

PAPER Are Bit Vectors Optimal by Buhrman, Miltersen, Radhakrishnan, Venkatesh BITVECTOPT.PS,

CELL PROBE- NON-BIT COMPLEXITY

NOTES ON RAMSEY THEORY (NEEDED FOR YAO PAPER) RAMSEY.PDF, RAMSEY.PS,

NOTE ON YAO'S PAPER SHOULD TABLES BE SORTED CELLYAO.PDF, CELLYAO.PS,

PAPER Should Tables be Sorted by Yao TABLES.PDF,TABLES.PS.

PAPER Storing a Sparse Table in O(1) Worst Case Access Time by Fredman, Komlos, Szemeredi. FKS.PDF

NOTES ON POLY EVAL CELLPOLY.PDF, CELLPOLY.PS,

PAPER On the Cell Probe Complexity of Poly Eval by Miltersen POLYEVALMILT.PDF POLYEVALMILT.PS

PAPER The Cell Probe Complexity of Succint Data Structures by Gal and Miltersen GALMILT.PDF GALMILT.PS

PRIVATE INFORMATION RETRIEVAL

PAPER Private Information Retrieval by Chor, Goldreich, Kushilevits, Sudan PIRFIRST.PDF

PAPER Upper Bounds on the Communication Complexity of Private Information Retrieval by Ambainis PIRAMB.PS

AN APPLICATION OF RAMSEY"S THEOREM TO COMM COMP

NOTES ON THE APPLICATION: APPRAMSEY.PDF, APPRAMSEY.PS,

PAPER An Application of Hindman's Theorem to Comm. Comp. HIND.PDF, HIND.PS,

HOMEWORKS

hw01.PDF, hw01.PS, hw01sol.PDF, hw01sol.PS.

hw02.PDF, hw02.PS, hw02sol.PDF, hw02sol.PS

hw03.PDF, hw03.PS

hw04.PDF, hw04.PS, hw04sol.PDF, hw04sol.PS

hw05.PDF, hw05.PS, hw05sol.PDF, hw05sol.PS

hw06.PDF, hw06.PS

hw07.PDF, hw07.PS, hw07sol.PDF, hw07sol.PS

mid.PDF, mid.PS, midsol.PDF, midsol.PS

hw08.PDF, hw08.PS

makemid.PDF, makemid.PS,

hw09.PDF, hw09.PS hw09sol.PDF, hw09sol.PS

hw10.PDF, hw10.PS

hw11.PDF, hw11.PS

hw12.PDF, hw12.PS

polyprob.PDF, polyprob.PS