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] | |
  | |