|
|
I am a
postdoctoral researcher at the Microsoft
Research New
England lab.
I am interested in complexity theory, the theory of real computation, machine learning, algorithms, and game theory. My e-mail address: #######@cs.toronto.edu, replacing "#######" with "mbraverm" This year, I am on the PC of FOCS'09 and on the PC of CCA'09. |
|
|
||
Papers | ||||
| The complexity of simulating Brownian Motion | ||||
| Ilia Binder, Mark Braverman | ||||
| SODA 2009 | [pdf] | |||
| Noisy Sorting Without Resampling | ||||
| Mark Braverman, Elchanan Mossel | ||||
| SODA 2008 | [arXiv.org] | |||
| Mafia : A Theoretical Study Of Players and Coalitions in a Partial Information Environment | ||||
| Mark Braverman, Omid Etesami, Elchanan Mossel | ||||
| Annals of Appl. Prob. 18(3), 2008 | [arXiv.org] | |||
| Derandomizing Euclidean random walks | ||||
| Ilia Binder, Mark Braverman | ||||
| RANDOM 2007 | [ps] [pdf] | |||
| Constructing Non-Computable Julia Sets | ||||
| Mark Braverman, Michael Yampolsky | ||||
| STOC 2007 | [ps] [pdf] | |||
| Parity Problems in Planar Graphs | ||||
| Mark Braverman, Raghav Kulkarni, Sambuddha Roy | ||||
| Complexity 2007 | [ps] [pdf] | |||
| Full version | [ECCC] | |||
| Termination of Integer Linear Programs | ||||
| Mark Braverman | ||||
| CAV (Computer-Aided Verification) 2006 | [pdf] | |||
| Non-Computable Julia Sets | ||||
| Mark Braverman, Michael Yampolsky | ||||
| Journ. Amer. Math. Soc. 19(3) | [arXiv.org] | |||
| Computing over the Reals: Foundations for Scientific Computing | ||||
| Mark Braverman, Stephen Cook | ||||
| Notices of the AMS, 53(3), March 2006 | [arXiv.org] | |||
| On computational complexity of Riemann mapping | ||||
| Ilia Binder, Mark Braverman, Michael Yampolsky | ||||
| Arkiv for Matematik, to appear | [arXiv.org] | |||
| Parabolic Julia Sets are Polynomial Time Computable | ||||
| Mark Braverman | ||||
| Nonlinearity 19, 2006 | [arXiv.org] | |||
| Filled Julia sets with empty interior are computable | ||||
| Ilia Binder, Mark Braverman, Michael Yampolsky | ||||
| Journal of Found. of Comp. Math., to appear | [arXiv.org] | |||
| On computational complexity of Siegel Julia sets | ||||
| Ilia Binder, Mark Braverman, Michael Yampolsky | ||||
| Commun. Math. Physics, 264(2), 2006 | [arXiv.org] | |||
| New results on hardness of proper learning and beyond | ||||
| Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi | ||||
| Journal of Computer and System Sciences, to appear | [ps] | |||
| On the Complexity of Real Functions | ||||
| Mark Braverman | ||||
| FOCS 2005 | [pdf] | |||
| Full version | [arXiv.org] | |||
| Learnability and Automatizability | ||||
| Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi | ||||
| FOCS 2004 | [ps] | |||
| Hyperbolic Julia sets are poly-time computable | ||||
| Mark Braverman | ||||
| CCA (Computability and Complexity in Analysis) 2004, ENTCS 120 | [ps][pdf] | |||
Manuscripts | ||||
| Direct Sums in Randomized Communication Complexity | ||||
| Boaz Barak, Mark Braverman, Xi Chen, Anup Rao | ||||
| [ECCC] | ||||
| Finding low error clusterings | ||||
| Nina Balcan, Mark Braverman | ||||
| Submitted | [pdf] | |||
| Poly-logarithmic independence fools AC0 circuits | ||||
| Mark Braverman | ||||
| (updated April 30, 2009) | [pdf] | |||
| [ECCC] | ||||
| On ad hoc routing with guaranteed delivery | ||||
| Mark Braverman | ||||
| [arXiv.org] | ||||
| Computability of Julia Sets | ||||
| Mark Braverman, Michael Yampolsky | ||||
| Submitted | [arXiv.org] | |||
| Method of registering and aligning multiple images | ||||
| Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic, Vyacheslav Zavadsky | ||||
| Semiconductor Insights Inc. | ||||
| US patent application 20060257051 | [USPTO] | |||
| Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable | ||||
| Mark Braverman | ||||
| M.Sc. Thesis | [ps] [pdf] | |||
Computability and Complexity in Analysis and Dynamics Seminar page
Theory Student Seminar is now organized by Siavosh Benabbas
