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