| Matching with couples revisited |
| |
Itai Ashalgi,
Mark Braverman,
Avinatan Hassidim |
|
|
| |
Working paper
|
[pdf]
| |
| | |
| 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]
| |
| | |
| Approximate Nash equilibria under stability conditions |
| |
Nina Balcan, Mark Braverman |
|
|
| | Working paper |
[arXiv] | |
| | |
|
Computability of Brolin-Lyubich measure
|
| |
Ilia Binder,
Mark Braverman,
Cristobal Rojas,
Michael Yampolsky |
|
|
| | Submitted
| [arXiv]
| |
| | |
| The rate of convergence of the Walk on Spheres Algorithm |
| |
Ilia Binder,
Mark Braverman |
|
|
| |
Geometric and Functional Analysis, accepted |
[pdf] | |
| | |
|
Thurston equivalence to a rational map is decidable
|
| |
Sylvain Bonnot ,
Mark Braverman,
Michael Yampolsky |
|
|
| | Preprint
| [arXiv]
| |
| | |
| 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]
| |
| | |
| Phylogenetic Reconstruction with Insertions and Deletions |
| |
Alex Andoni,
Mark Braverman,
Avinatan Hassidim
|
|
|
| | Working paper |
[pdf]
| |
| | |
| Monotonicity and Implementability |
| |
Itai Ashalgi,
Mark Braverman,
Avinatan Hassidim,
Dov Monderer
|
|
|
| |
Econometrica, forthcoming
|
[pdf]
| |
| | |
|
Sorting from Noisy Information |
| | Mark Braverman,
Elchanan Mossel
|
| | Submitted |
[arXiv] [bib]
| |
| | |
| Ascending unit demand auctions with budget limits |
| |
Itai Ashalgi,
Mark Braverman,
Avinatan Hassidim
|
|
|
| |
Working paper
|
[pdf]
| |
| | |
| Position Auctions with Budgets: Existence and Uniqueness |
| |
Itai Ashalgi,
Mark Braverman,
Avinatan Hassidim, Ron Lavi,
Moshe Tennenholtz
|
|
|
| | The
B.E. Journal of Theoretical Economics (Advances), 10(1),
Article 20, 2010 |
[pdf]
| |
| | |
| Poly-logarithmic independence fools AC0 circuits |
| | Mark Braverman
|
|
|
| | Complexity 2009 |
[pdf] [ECCC]
[bib]
| |
| | To appear in Journal of the ACM |
| |
| | |
| Finding low error clusterings |
| |
Nina Balcan, Mark Braverman |
|
|
| | COLT 2009 |
[pdf] [bib] | |
| | |
| The complexity of simulating Brownian Motion |
| |
Ilia Binder,
Mark Braverman |
|
|
| | SODA 2009 |
[pdf] [bib] | |
| | |
| Constructing Locally Connected Non-Computable Julia Sets |
| |
Mark Braverman,
Michael Yampolsky |
|
|
| | Commun. Math. Physics, 291(2), 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]
| |
| | |
|
Noisy Sorting Without Resampling
|
| | Mark Braverman,
Elchanan Mossel
|
| | SODA 2008 |
[arXiv]
[bib]
| |
| | |
| 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]
[bib]
| |
| | |
| 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] | |
| | |
| Computability of Julia
Sets |
| | Mark Braverman,
Michael Yampolsky |
|
|
| | Moscow Math. Journal 8(2), 2008 |
[arXiv][bib] | |
| | |
| Derandomizing Euclidean random walks |
| |
Ilia Binder,
Mark Braverman |
|
|
| | RANDOM 2007 |
[pdf]
[bib] | |
| | |
| Constructing Non-Computable Julia
Sets |
| | Mark Braverman,
Michael Yampolsky |
|
|
| | STOC 2007 |
[pdf] [bib] | |
| | |
| Parity
Problems in Planar Graphs |
| | Mark Braverman,
Raghav Kulkarni,
Sambuddha Roy
|
| | Complexity 2007 |
[pdf]
[bib] | |
| | |
| Filled Julia sets with
empty interior are computable |
| |
Ilia Binder,
Mark Braverman,
Michael Yampolsky |
|
|
| | Journal of
Found. of Comp. Math. 7(4),
2007 |
[arXiv]
[bib] | |
| | |
| On computational
complexity of Riemann mapping |
| |
Ilia Binder,
Mark Braverman,
Michael Yampolsky |
|
|
| | Arkiv for Matematik, 45(2), 2007 |
[arXiv][bib] | |
| | |
| Termination of Integer Linear Programs |
| | Mark Braverman | |
| | CAV (Computer-Aided Verification) 2006 |
[pdf] [bib] | |
| | |
| Non-Computable Julia
Sets |
| | Mark Braverman,
Michael Yampolsky |
|
|
| | Journ. Amer. Math. Soc.
19(3), 2006 |
[arXiv][bib] | |
| | |
| Computing over the Reals: Foundations
for Scientific Computing |
| | Mark Braverman,
Stephen Cook |
| |
| | Notices of the
AMS, 53(3),
March 2006 |
[arXiv]
[bib] | |
| | |
| Parabolic Julia Sets are Polynomial Time Computable |
| | Mark Braverman | |
| | Nonlinearity 19, 2006 |
[arXiv][bib] | |
| | |
| On computational
complexity of Siegel Julia sets |
| |
Ilia Binder,
Mark Braverman,
Michael Yampolsky |
|
|
| | Commun. Math. Physics, 264(2), 2006 |
[arXiv] [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] | |
| | |
| Hyperbolic Julia sets are poly-time
computable |
| | Mark Braverman | |
| | CCA (Computability and Complexity in Analysis) 2004,
ENTCS
120 |
[pdf] [bib] | |
