| Towards coding for maximum errors in interactive communication | ||||
| Mark Braverman, Anup Rao | ||||
| Submitted | [ECCC] | |||
| Information equals amortized communication | ||||
| Mark Braverman, Anup Rao | ||||
| submitted | [pdf] | |||
| Earlier version (under a different title) | [ECCC] | |||
| Pseudorandom Generators for Regular Branching Programs | ||||
| Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff | ||||
| FOCS'10 | [ECCC] | |||
| How to compress interactive communication | ||||
| Boaz Barak, Mark Braverman, Xi Chen, Anup Rao | ||||
| STOC'10, invited to the special issue of SICOMP | [pdf] | |||
| Previous version | [ECCC] | |||
| Poly-logarithmic independence fools AC0 circuits | ||||
| Mark Braverman | ||||
| Complexity 2009 | [pdf] [ECCC] [bib] | |||
| To appear in Journal of the ACM | ||||
| The complexity of simulating Brownian Motion | ||||
| Ilia Binder, Mark Braverman | ||||
| SODA 2009 | [pdf] [bib] | |||
| Space-Efficient Counting in Graphs on Surfaces | ||||
| Mark Braverman, Raghav Kulkarni, Sambuddha Roy | ||||
| Computational Complexity 18(4), 2009 | [pdf] [bib] | |||
| Branching Programs for Tree Evaluation | ||||
| Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam , Dustin Wehr | ||||
| MFCS 2009 | [pdf] [bib] | |||
| Full version | [pdf] | |||
| Slides from Steve Cook's talk with a $100 prize offer | [ps] | |||
| On ad hoc routing with guaranteed delivery | ||||
| Mark Braverman | ||||
| Brief announcement, PODC 2008 | [arXiv][bib] | |||
| The complexity of properly learning simple concept classes | ||||
| Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi | ||||
| Journal of Computer and System Sciences, 74(1), 2008 | [pdf] [bib] | |||
| Derandomizing Euclidean random walks | ||||
| Ilia Binder, Mark Braverman | ||||
| RANDOM 2007 | [pdf] [bib] | |||
| Parity Problems in Planar Graphs | ||||
| Mark Braverman, Raghav Kulkarni, Sambuddha Roy | ||||
| Complexity 2007 | [pdf] [bib] | |||
| On the Complexity of Real Functions | ||||
| Mark Braverman | ||||
| FOCS 2005 | [pdf] [bib] | |||
| Full version | [arXiv] | |||
| Learnability and Automatizability | ||||
| Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi | ||||
| FOCS 2004 | [pdf] [bib] | |||