|
|
I am a Ph.D. student in the Dept. of Computer Science at the University of Toronto supervised by Stephen Cook. I am interested in complexity theory, especially in the theory of real computation. Computability and Complexity in Analysis and Dynamics Seminar page Theory Student Seminar is now organized by Siavosh Benabbas My e-mail address: #######@cs.toronto.edu, replacing "#######" with "mbraverm" |
Papers | ||||
| 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., to appear | [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 | ||||
| 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] | |||
