Mark Braverman's Home Page - Research

Research.AllPapers History

Hide minor edits - Show changes to output - Cancel

September 17, 2013, at 02:40 PM EST by admin -

Added lines 4-7:

* Public vs private coin in bounded-round information\\
Mark Braverman, Ankit Garg \\
[[http://eccc.hpi-web.de/report/2013/130/| [ECCC] ]]

Restore

July 22, 2013, at 12:44 AM EST by admin -

Added lines 4-7:

* Optimal Provision-After-Wait in healthcare\\
Mark Braverman, Jing Chen, Sampath Kannan \\
''working paper''; [[Attach:BCKhealth_V1.pdf| [pdf] ]]

Restore

June 25, 2013, at 01:25 PM EST by admin -

Changed lines 7-8 from:

[[http://arxiv.org/abs/1305.4696| [arXiv] ]]

to:

FOCS'13; [[http://arxiv.org/abs/1305.4696| [arXiv] ]]

* Direct products in communication complexity\\
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff \\
FOCS'13; [[http://eccc.hpi-web.de/report/2012/143/| [ECCC] ]]

Deleted lines 31-34:

* Direct products in communication complexity\\
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff \\
[[http://eccc.hpi-web.de/report/2012/143/| [ECCC] ]]

Restore

June 20, 2013, at 11:12 PM EST by admin -

Changed line 15 from:

[[http://eccc.hpi-web.de/report/2013/035/| [ECCC] ]]

to:

ICALP'13; [[http://eccc.hpi-web.de/report/2013/035/| [ECCC] ]]

Restore

May 22, 2013, at 06:09 PM EST by admin -

Added lines 4-7:

* Tight bounds for set disjointness in the message passing model \\
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan \\
[[http://arxiv.org/abs/1305.4696| [arXiv] ]]

Restore

March 07, 2013, at 03:52 PM EST by admin -

Added lines 8-11:

* Direct product via round-preserving compression \\
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff \\
[[http://eccc.hpi-web.de/report/2013/035/| [ECCC] ]]

Restore

February 13, 2013, at 01:13 PM EST by admin -

Changed line 74 from:

~~Preprint~~; [[http://arxiv.org/abs/1202.2097 | [arXiv] ]]

to:

WWW'13; [[http://arxiv.org/abs/1202.2097 | [arXiv] ]]

Restore

February 13, 2013, at 12:28 PM EST by admin -

Changed lines 7-8 from:

[[http://eccc.hpi-web.de/report/2012/171/| [ECCC] ]]

to:

STOC'13; [[http://eccc.hpi-web.de/report/2012/171/| [ECCC] ]]

Changed lines 11-12 from:

[[http://eccc.hpi-web.de/report/2012/177/| [ECCC] ]]

to:

CSR'13; [[http://eccc.hpi-web.de/report/2012/177/| [ECCC] ]]

Changed line 27 from:

[[http://eccc.hpi-web.de/report/2012/131/| [ECCC] ]]

to:

STOC'13; [[http://eccc.hpi-web.de/report/2012/131/| [ECCC] ]]

Restore

February 05, 2013, at 11:59 PM EST by admin -

Changed line 15 from:

[[http://arxiv.org/abs/1302.0892| [arXiv] ]]

to:

STACS'13; [[http://arxiv.org/abs/1302.0892| [arXiv] ]]

Restore

February 05, 2013, at 11:58 PM EST by admin -

Added lines 13-15:

* Search using queries on indistinguishable items\\
Mark Braverman, Gal Oshri \\
[[http://arxiv.org/abs/1302.0892| [arXiv] ]]

Restore

January 28, 2013, at 11:11 PM EST by admin -

Changed line 76 from:

[[http://theoryofcomputing.org/|''Theory of Computing'']], ~~to appear~~

to:

[[http://theoryofcomputing.org/|''Theory of Computing'']], [[http://theoryofcomputing.org/articles/v009a003/|'''9'''(3)]], 2013.

Restore

December 20, 2012, at 09:57 AM EST by admin -

Added lines 8-12:

* Information lower bounds via self-reducibility\\
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein \\
[[http://eccc.hpi-web.de/report/2012/177/| [ECCC] ]]

Restore

December 03, 2012, at 02:17 PM EST by admin -

Added lines 4-7:

* From information to exact communication\\
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein \\
[[http://eccc.hpi-web.de/report/2012/171/| [ECCC] ]]

Restore

November 08, 2012, at 11:13 PM EST by admin -

Added lines 4-7:

* On the convergence of the Hegselmann-Krause system \\
Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy Nguyen \\
ITCS'13; [[http://arxiv.org/abs/1211.1909| [arXiv] ]]

Restore

November 05, 2012, at 10:19 PM EST by admin -

Changed line 5 from:

* ~~An information complexity approach to extended formulations~~\\

to:

* Direct products in communication complexity\\

Restore

November 05, 2012, at 10:19 PM EST by admin -

Added lines 4-7:

* An information complexity approach to extended formulations\\
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff \\
[[http://eccc.hpi-web.de/report/2012/143/| [ECCC] ]]

Restore

October 22, 2012, at 11:37 AM EST by admin -

Added lines 8-11:

* Coding for interactive computation: progress and challenges\\
Mark Braverman\\
Allerton'12; [[Attach:Interactive-Allerton12-Braverman.pdf| [pdf] ]]

Restore

October 22, 2012, at 11:35 AM EST by admin -

Changed line 46 from:

'~~'Working paper''~~; [[http://arxiv.org/abs/1201.4899| [arXiv] ]]

to:

SODA'13; [[http://arxiv.org/abs/1201.4899| [arXiv] ]]

Restore

October 22, 2012, at 11:35 AM EST by admin -

Added lines 4-7:

* An information complexity approach to extended formulations\\
Mark Braverman, Ankur Moitra \\
[[http://eccc.hpi-web.de/report/2012/131/| [ECCC] ]]

Restore

June 19, 2012, at 02:13 AM EST by admin -

Changed lines 113-114 from:

''Communications of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011. \\
Lecture video from the 2011 METRIC workshop (audio quality not great): [[http://www.dailymotion.com/video/xhwee1_metric-2011-mark-braverman_tech| [video]]].

to:

''Communications of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011 \\
Lecture video from the 2011 METRIC workshop (audio quality not great): [[http://www.dailymotion.com/video/xhwee1_metric-2011-mark-braverman_tech| [video] ]]

Restore

June 19, 2012, at 02:12 AM EST by admin -

Changed line 114 from:

Lecture video from the 2011 METRIC workshop (audio quality not great): [[http://www.dailymotion.com/video/xhwee1_metric-2011-mark-braverman_tech| ~~Video~~]].

to:

Lecture video from the 2011 METRIC workshop (audio quality not great): [[http://www.dailymotion.com/video/xhwee1_metric-2011-mark-braverman_tech| [video]]].

Restore

June 19, 2012, at 02:12 AM EST by admin -

Changed lines 113-114 from:

''Communications of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011.

to:

Restore

June 07, 2012, at 06:07 PM EST by admin -

Changed line 15 from:

~~Submitted~~; [[http://eccc.hpi-web.de/report/2011/164/ | [ECCC] ]]

to:

RANDOM'12; [[http://eccc.hpi-web.de/report/2011/164/ | [ECCC] ]]

Restore

May 13, 2012, at 03:57 PM EST by admin -

Changed lines 218-222 from:

* Predicting web advertisement click success by using head-to-head ratings \\
Mohsen Bayati, Mark Braverman, Satyen Kale, Yury Makarychev \\
US patent application 20100198685; [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&s1=20100198685.PGNR.|[USPTO] ]]

to:

Added lines 228-231:

* Health care policy development and execution \\
Mohsen Bayati, Mark Braverman, Eric Horvitz, Michael Gillam \\
US patent application 20120004925; [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&s1=20120004925.PGNR.|[USPTO] ]]

Added lines 239-242:

Restore

May 13, 2012, at 03:55 PM EST by admin -

Added lines 217-221:

Restore

May 13, 2012, at 03:52 PM EST by admin -

Added lines 226-229:

* Dispensing digital objects to an electronic wallet \\
Philipp Hertel, Alex Hertel, John Graham, Mark Braverman \\
US patent application 20110145049; [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&s1=20110145049.PGNR.|[USPTO] ]]

Restore

May 13, 2012, at 03:47 PM EST by admin -

Changed line 225 from:

PhD Thesis ~~[[Attach:PHD-thesis.pdf| [pdf] ]]~~

to:

PhD Thesis

Restore

May 13, 2012, at 03:41 PM EST by admin -

Changed lines 133-135 from:

''ACM Transactions on Computation Theory (TOCT)'' [[http://dl.acm.org/citation.cfm?id=2077336&picked=prox&CFID=81870375&CFTOKEN=22307623| '''3'''(2)]], 2012; [[~~Attach~~:~~branching~~.~~pdf~~|[~~pdf~~] ]]\\
''Preliminary version'': MFCS'09\\
Slides from Steve Cook'~~s talk with a \$100 prize offer~~ [[Attach:pebblingSlides.ps|[ps] ]]

to:

''ACM Transactions on Computation Theory (TOCT)'' [[http://dl.acm.org/citation.cfm?id=2077336&picked=prox&CFID=81870375&CFTOKEN=22307623| '''3'''(2)]], 2012; [[http://arxiv.org/abs/1005.2642|[arXiv] ]]\\
''Preliminary version'': MFCS'09 and FSTTCS'09\\
Slides from Steve Cook's talk with a \$100 prize offer [[Attach:pebblingSlides.pdf|[pdf] ]]

Restore

May 13, 2012, at 03:30 PM EST by admin -

Changed line 133 from:

''ACM Transactions on Computation Theory (TOCT)'' [[http://dl.acm.org/citation.cfm?id=2077336&picked=prox&CFID=81870375&CFTOKEN=22307623| '''3'''(2)]], 2012; [[Attach:branching.pdf]]\\

to:

''ACM Transactions on Computation Theory (TOCT)'' [[http://dl.acm.org/citation.cfm?id=2077336&picked=prox&CFID=81870375&CFTOKEN=22307623| '''3'''(2)]], 2012; [[Attach:branching.pdf|[pdf] ]]\\

Restore

May 13, 2012, at 03:20 PM EST by admin -

Changed line 184 from:

CAV'06 (Computer-Aided Verification) | [[Attach:terminationCAV.pdf|[pdf] ]]

to:

CAV'06 (Computer-Aided Verification); [[Attach:terminationCAV.pdf|[pdf] ]]

Restore

May 13, 2012, at 03:14 PM EST by admin -

Changed line 95 from:

''Econometrica'' [[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |'''78'''(5)]], 2010; [[Attach:Mon.pdf | [pdf] ]]

to:

''Econometrica'' [[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |'''78'''(5)]], 2010; [[Attach:Mon.pdf | [pdf] ]] [[Attach:Mon-Supp.pdf| [Supplementary material] ]]

Restore

May 13, 2012, at 03:09 PM EST by admin -

Changed line 84 from:

* ~~Matching with couples revisited~~\\

to:

* Stability in large matching markets with complementarities \\

Restore

May 13, 2012, at 02:58 PM EST by admin -

Added lines 39-42:

* Finding endogenously formed communities\\
Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, Shang-Hua Teng\\
''Working paper''; [[http://arxiv.org/abs/1201.4899| [arXiv] ]]

Restore

May 13, 2012, at 02:57 PM EST by admin -

Changed lines 46-47 from:

in APPROX'11; [[http://arxiv.org/abs/1104.3760| arXiv]] \\
[[http://theoryofcomputing.org/|Theory of Computing]], to appear

to:

in APPROX'11; [[http://arxiv.org/abs/1104.3760| [arXiv] ]] \\
[[http://theoryofcomputing.org/|''Theory of Computing'']], to appear

Restore

May 13, 2012, at 02:57 PM EST by admin -

Added lines 44-47:

* Inapproximability of NP-complete variants of Nash equilibrium \\
Per Austrin, Mark Braverman, Eden Chlamtac\\
in APPROX'11; [[http://arxiv.org/abs/1104.3760| arXiv]] \\
[[http://theoryofcomputing.org/|Theory of Computing]], to appear

Restore

May 13, 2012, at 02:51 PM EST by admin -

Added lines 36-38:

* Leaky pseudo-entropy functions \\
Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai \\
In [[http://conference.itcs.tsinghua.edu.cn/ICS2011/content/paper/17.pdf | ITCS'11]]; [[Attach:pseudoentropy.pdf|[pdf] ]]

Restore

May 13, 2012, at 02:00 AM EST by admin -

Deleted line 217:

~~Google Inc. \\~~

Restore

May 13, 2012, at 01:56 AM EST by admin -

Added lines 216-221:

* Secured electronic transaction system \\
Philipp Hertel, Alex Hertel, John Graham, Mark Braverman \\
Google Inc. \\
US patent application 20090288012 [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&s1=20090288012.PGNR.|[USPTO] ]]

Changed line 225 from:

US patent 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

to:

US patent 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

Restore

May 13, 2012, at 01:54 AM EST by admin -

Deleted lines 206-210:

* Method of registering and aligning multiple images\\
Vyacheslav Zavadsky, Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic \\
Semiconductor Insights Inc.\\
US patent 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

Changed lines 209-220 from:

~~M.Sc.~~ Thesis [pdf]

to:

MSc Thesis [[Attach:MSC-thesis.pdf| [pdf] ]]

* Computability and complexity of Julia sets \\
Mark Braverman\\
PhD Thesis [[Attach:PHD-thesis.pdf| [pdf] ]]

* Method of registering and aligning multiple images\\
Vyacheslav Zavadsky, Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic \\
Semiconductor Insights Inc.\\
US patent 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

Restore

May 13, 2012, at 01:51 AM EST by admin -

Changed line 210 from:

US patent ~~application~~ 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

to:

US patent 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

Restore

May 13, 2012, at 01:51 AM EST by admin -

Changed line 208 from:

~~Jason Abt~~, ~~Mark Braverman~~, ~~Edward Keyes~~, ~~Vladimir Martincevic~~, ~~Vyacheslav Zavadsky~~\\

to:

Vyacheslav Zavadsky, Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic \\

Changed line 210 from:

US patent application ~~20060257051~~ [USPTO]

to:

US patent application 7,693,348 [[http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7693348|[USPTO] ]]

Restore

May 13, 2012, at 01:48 AM EST by admin -

Changed lines 171-173 from:

* Termination of Integer Linear Programs
~~Mark~~ Braverman
~~CAV (Computer-Aided Verification) 2006 [pdf] [bib~~]

to:

* Termination of Integer Linear Programs \\
Mark Braverman \\
CAV'06 (Computer-Aided Verification) | [[Attach:terminationCAV.pdf|[pdf] ]]

Changed line 177 from:

Journ. Amer. Math. Soc. 19(3), 2006 [~~arXiv]~~[~~bib]~~

to:

''Journ. Amer. Math. Soc.'' '''19'''(3), 2006; [[ http://arxiv.org/abs/math.DS/0406416 |[arXiv] ]]

Changed line 181 from:

Notices of the AMS, ~~53(3), March 2006~~ [~~arXiv]~~ [~~bib~~]

to:

''Notices of the AMS'', [[http://www.ams.org/notices/200603/fea-cook.pdf|'''53'''(3)]], March 2006; [[http://arxiv.org/abs/cs.CC/0509042|[arXiv] ]]

Changed line 185 from:

Nonlinearity 19, 2006 [~~arXiv]~~[~~bib~~]

to:

''Nonlinearity'' '''19''', 2006; [[http://arxiv.org/abs/math/0505036|[arXiv] ]]

Changed line 189 from:

Commun. Math. Physics, 264(2), 2006 [~~arXiv]~~ [~~bib~~]

to:

''Commun. Math. Physics'', '''264'''(2), 2006; [[http://arxiv.org/abs/math/0502354|[arXiv] ]]

Changed lines 193-194 from:

FOCS ~~2005~~ [pdf] ~~[bib~~]\\
Full version [arXiv]

to:

FOCS'05 [[Attach:realFunctions05.pdf|[pdf] ]] \\
Full version [[http://arxiv.org/abs/cs.CC/0502066|[arXiv] ]]

Changed line 198 from:

FOCS ~~2004~~ [pdf] ~~[bib~~]

to:

FOCS'04; [[Attach:learnabilityAutomatizability.pdf|[pdf] ]]

Changed line 202 from:

CCA (Computability and Complexity in Analysis) ~~2004~~, ENTCS 120 [pdf] ~~[bib~~]

to:

CCA'04 (Computability and Complexity in Analysis), ''ENTCS'' '''120'''; [[Attach:hyperbolic.pdf|[pdf] ]]

Restore

May 13, 2012, at 01:36 AM EST by admin -

Changed lines 163-165 from:

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

to:

* Filled Julia sets with empty interior are computable \\
Ilia Binder, Mark Braverman, Michael Yampolsky \\
''Journal of Found. of Comp. Math.'' '''7'''(4), 2007; [[http://arxiv.org/abs/math.DS/0410580 |[arXiv] ]]

Changed lines 167-169 from:

* On computational complexity of Riemann mapping
~~Ilia~~ Binder, Mark Braverman, Michael Yampolsky
~~Arkiv for Matematik,~~ 45(2), 2007 [~~arXiv]~~[~~bib~~]

to:

* On computational complexity of Riemann mapping \\
Ilia Binder, Mark Braverman, Michael Yampolsky \\
''Arkiv for Matematik'', '''45'''(2), 2007; [[http://arxiv.org/abs/math.CV/0505617|[arXiv] ]]

Restore

May 13, 2012, at 01:32 AM EST by admin -

Changed lines 143-145 from:

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

to:

* 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; [[Attach:ABFKP_Proper_Hardness_08.pdf|[pdf] ]]

Changed lines 147-149 from:

* Computability of Julia Sets
~~Mark~~ Braverman, Michael Yampolsky
~~Moscow Math. Journal~~ 8(2), 2008 [~~arXiv]~~[~~bib~~]

to:

* Computability of Julia Sets \\
Mark Braverman, Michael Yampolsky \\
''Moscow Math. Journal'' '''8'''(2), 2008; [[http://arxiv.org/abs/math.DS/0610340|arXiv]]

Changed lines 151-153 from:

* Derandomizing Euclidean random walks
~~Ilia~~ Binder, Mark Braverman
~~RANDOM 2007~~ [pdf] ~~[bib~~]

to:

* Derandomizing Euclidean random walks \\
Ilia Binder, Mark Braverman \\
RANDOM'07; [[Attach:euclidian.pdf|[pdf] ]]

Changed lines 155-157 from:

* Constructing Non-Computable Julia Sets
~~Mark~~ Braverman, Michael Yampolsky
~~STOC 2007~~ [pdf] ~~[bib~~]

to:

* Constructing Non-Computable Julia Sets \\
Mark Braverman, Michael Yampolsky \\
STOC'07; [[Attach:constructingJulia.pdf|[pdf] ]]

Changed lines 159-161 from:

* Parity Problems in Planar Graphs
~~Mark~~ Braverman, Raghav Kulkarni, Sambuddha Roy
~~Complexity 2007~~ [pdf] ~~[bib~~]

to:

* Parity Problems in Planar Graphs \\
Mark Braverman, Raghav Kulkarni, Sambuddha Roy \\
Complexity'07; [[Attach:planarParity.pdf|[pdf] ]]

Restore

May 11, 2012, at 05:13 PM EST by admin -

Changed line 124 from:

Slides from Steve Cook's talk with a $\$100~~\sum $~~ prize offer [[Attach:pebblingSlides.ps|[ps] ]]

to:

Slides from Steve Cook's talk with a \$100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Restore

May 11, 2012, at 05:13 PM EST by admin -

Changed line 124 from:

Slides from Steve Cook's talk with a $\$100$ prize offer [[Attach:pebblingSlides.ps|[ps] ]]

to:

Slides from Steve Cook's talk with a $\$100\sum $ prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Restore

May 11, 2012, at 05:11 PM EST by admin -

Restore

May 11, 2012, at 05:10 PM EST by admin -

Changed line 124 from:

Slides from Steve Cook's talk with a ~~$~~100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

to:

Slides from Steve Cook's talk with a $\$100$ prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Restore

May 11, 2012, at 12:24 AM EST by admin -

Changed line 127 from:

*[[ |Book]]: Computability of Julia Sets\\

to:

*[[ Research.Book|Book]]: Computability of Julia Sets\\

Changed lines 139-141 from:

* On ad hoc routing with guaranteed delivery
~~Mark~~ Braverman
~~Brief announcement, PODC 2008 [arXiv~~]~~[bib~~]

to:

* On ad hoc routing with guaranteed delivery \\
Mark Braverman \\
Brief announcement, PODC'08; [[ http://arxiv.org/abs/0804.0862|[arXiv] ]]

Restore

May 11, 2012, at 12:22 AM EST by admin -

Changed line 124 from:

Slides from Steve Cook's talk with a &#~~198~~ 100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

to:

Slides from Steve Cook's talk with a $100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Changed lines 127-129 from:

!!! 2004-2008

*Book: Computability of Julia Sets\\

to:

*[[ |Book]]: Computability of Julia Sets\\

Changed lines 129-134 from:

Springer, 2008
[Amazon] [Springer]

* Noisy Sorting Without Resampling
Mark Braverman, Elchanan Mossel
SODA ~~2008 [arXiv] [bib]~~

to:

Springer, 2009.

* Noisy Sorting Without Resampling \\
Mark Braverman, Elchanan Mossel \\
SODA'08.

Changed lines 135-137 from:

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

to:

* 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; [[http://arxiv.org/abs/math.PR/0609534|[arXiv] ]]

Restore

May 11, 2012, at 12:18 AM EST by admin -

Changed line 124 from:

Slides from Steve Cook's talk with a $100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

to:

Slides from Steve Cook's talk with a &#198 100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Restore

May 11, 2012, at 12:15 AM EST by admin -

Changed lines 116-118 from:

* Space-Efficient Counting in Graphs on Surfaces
~~Mark Braverman~~, Raghav Kulkarni, Sambuddha Roy
Computational Complexity 18(4), 2009 [pdf] ~~[bib~~]

to:

* Space-Efficient Counting in Graphs on Surfaces\\
Mark Braverman, Raghav Kulkarni, Sambuddha Roy \\
''Computational Complexity'' '''18'''(4), 2009; [[Attach:planarCounting.pdf|[pdf] ]]

Changed lines 120-124 from:

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

to:

* Pebbles and branching programs for tree evaluation \\
Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam \\
''ACM Transactions on Computation Theory (TOCT)'' [[http://dl.acm.org/citation.cfm?id=2077336&picked=prox&CFID=81870375&CFTOKEN=22307623| '''3'''(2)]], 2012; [[Attach:branching.pdf]]\\
''Preliminary version'': MFCS'09\\
Slides from Steve Cook's talk with a $100 prize offer [[Attach:pebblingSlides.ps|[ps] ]]

Restore

May 10, 2012, at 11:44 PM EST by admin -

Changed line 102 from:

''~~Communication~~ of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011.

to:

''Communications of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011.

Changed lines 104-106 from:

* Finding low error clusterings
~~Nina~~ Balcan, Mark Braverman
~~COLT 2009 [pdf~~] ~~[bib~~]

to:

* Finding low error clusterings \\
Nina Balcan, Mark Braverman \\
COLT'2009; [[Attach:clustering.pdf | [pdf] ]]

Changed lines 108-114 from:

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

to:

* The complexity of simulating Brownian Motion \\
Ilia Binder, Mark Braverman \\
SODA'09; [[Attach:BrownianMotion.pdf| [pdf] ]]

* Constructing Locally Connected Non-Computable Julia Sets \\
Mark Braverman, Michael Yampolsky \\
''Commun. Math. Physics'', '''291'''(2), 2009; [[Attach:locConn.pdf |[pdf] ]]

Restore

May 10, 2012, at 11:42 PM EST by admin -

Changed line 84 from:

''Econometrica'' [[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |'''78'''(5)]]; [[Attach:Mon.pdf | [pdf] ]]

to:

''Econometrica'' [[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |'''78'''(5)]], 2010; [[Attach:Mon.pdf | [pdf] ]]

Changed lines 98-101 from:

* Poly-logarithmic independence fools AC0 circuits
~~Mark~~ Braverman
~~Complexity 2009~~ [~~pdf]~~ [~~ECCC]~~ [~~bib~~]
~~To appear in Journal~~ of the ACM

to:

* Poly-logarithmic independence fools AC0 circuits \\
Mark Braverman \\
Complexity'09; [[http://eccc.hpi-web.de/report/2009/011/ |[ECCC] ]] \\
''Journal of the ACM'' [[http://dl.acm.org/citation.cfm?id=1754399&picked=prox&cfid=81870375&cftoken=22307623| '''57'''(5)]], 2010 \\
''Communication of the ACM'', research highlight, [[http://dl.acm.org/citation.cfm?id=1924421.1924446| '''54'''(4)]], 2011.

Restore

May 10, 2012, at 11:37 PM EST by admin -

Changed line 84 from:

[[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |''~~Econometrica~~'']]; [[Attach:Mon.pdf | [pdf] ]]

to:

''Econometrica'' [[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |'''78'''(5)]]; [[Attach:Mon.pdf | [pdf] ]]

Restore

May 10, 2012, at 11:36 PM EST by admin -

Changed lines 86-88 from:

* Sorting from Noisy Information
~~Mark~~ Braverman, Elchanan Mossel
~~Submitted~~ [~~arXiv]~~ [~~bib]~~

to:

* Sorting from Noisy Information \\
Mark Braverman, Elchanan Mossel \\
''Submitted''; [[ http://arxiv.org/abs/0910.1191| [arXiv] ]]

Changed lines 90-92 from:

* Ascending unit demand auctions with budget limits
~~Itai~~ Ashalgi, Mark Braverman, Avinatan Hassidim
~~Working paper~~ [pdf]

to:

* Ascending unit demand auctions with budget limits \\
Itai Ashalgi, Mark Braverman, Avinatan Hassidim \\
Working paper; [[ Attach:AscendingUnitDemand.pdf | [pdf] ]]

Changed lines 94-96 from:

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

to:

* 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), [[http://www.degruyter.com/view/j/bejte.2010.10.1/bejte.2010.10.1.1648/bejte.2010.10.1.1648.xml?format=INT| Article 20]], 2010; [[ Attach:positionAuctions.pdf | [pdf] ]].

Restore

May 10, 2012, at 11:30 PM EST by admin -

Changed line 79 from:

Alex Andoni, Mark Braverman, Avinatan Hassidim

to:

Alex Andoni, Mark Braverman, Avinatan Hassidim \\

Changed lines 82-83 from:

* Monotonicity and Implementability
~~Itai~~ Ashalgi, Mark Braverman, Avinatan Hassidim, Dov Monderer

to:

* Monotonicity and Implementability \\
Itai Ashalgi, Mark Braverman, Avinatan Hassidim, Dov Monderer \\

Restore

May 10, 2012, at 11:29 PM EST by admin -

Changed lines 78-80 from:

* Phylogenetic Reconstruction with Insertions and Deletions
~~Alex~~ Andoni, Mark Braverman, Avinatan Hassidim
~~Working paper~~ [pdf]

to:

* Phylogenetic Reconstruction with Insertions and Deletions \\
Alex Andoni, Mark Braverman, Avinatan Hassidim
Working paper [[Attach:phylo.pdf | [pdf] ]]

Changed lines 83-84 from:

~~Itai Ashalgi~~, ~~Mark Braverman~~, ~~Avinatan Hassidim, Dov Monderer~~
~~Econometrica, forthcoming~~ [~~pdf]~~

to:

Itai Ashalgi, Mark Braverman, Avinatan Hassidim, Dov Monderer
[[http://www.econometricsociety.org/abstract.asp?ref=0012-9682&vid=78&iid=5&aid=9&s=-9999 |''Econometrica'']]; [[Attach:Mon.pdf | [pdf] ]]

Restore

May 10, 2012, at 01:15 AM EST by admin -

Deleted lines 72-79:

\\ \\ \\ \\

* Phylogenetic Reconstruction with Insertions and Deletions\\
Alex Andoni, Mark Braverman, Avinatan Hassidim
Working paper
(:cell align=left:) [[Papers/phylo-10.pdf|[pdf]]]

Deleted lines 77-102:

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

Restore

May 10, 2012, at 01:14 AM EST by admin -

Restore

May 10, 2012, at 01:14 AM EST by admin -

Changed line 83 from:

Working paper [pdf]

to:

Working paper; [[Attach:ABH-couples.pdf|[pdf] ]]

Changed lines 85-92 from:

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

to:

Restore

May 09, 2012, at 11:11 PM EST by admin -

Deleted lines 62-68:

~~\\ \\ \\ \\~~

Changed lines 65-67 from:

~~Preprint [[http://arxiv~~.~~org~~/~~abs~~/~~1009~~.5713|[arXiv]]]

to:

''Moscow Math. Journal'', to appear; [[http://arxiv.org/abs/1009.5713|[arXiv] ]]

Changed line 69 from:

STOC'10~~, invited to the special issue of SICOMP~~ [[~~Papers/~~directsum.pdf|[pdf]]] \\

to:

STOC'10 [[Attach:directsum.pdf|[pdf] ]] \\

Added lines 71-73:

\\ \\ \\ \\

Restore

May 09, 2012, at 01:45 PM EST by admin -

Changed line 61 from:

''Geometric and Functional Analysis'', to appear; [[~~attach~~:AttachBBlocaldim.pdf|[pdf] ]]

to:

''Geometric and Functional Analysis'', to appear; [[Attach:AttachBBlocaldim.pdf|[pdf] ]]

Restore

May 09, 2012, at 01:44 PM EST by admin -

Changed line 61 from:

''Geometric and Functional Analysis'', to appear; [[attach:~~BBlocaldim~~.pdf|[pdf] ]]

to:

''Geometric and Functional Analysis'', to appear; [[attach:AttachBBlocaldim.pdf|[pdf] ]]

Restore

May 09, 2012, at 11:59 AM EST by admin -

Deleted lines 58-63:

~~\\ \\ \\ \\~~

Changed lines 61-63 from:

[[~~http~~:~~//www~~.~~springer.com/birkhauser/mathematics/journal/39~~|
~~Geometric and Functional Analysis~~]], accepted
[[Papers/BBlocaldim.pdf|[pdf]]]

to:

''Geometric and Functional Analysis'', to appear; [[attach:BBlocaldim.pdf|[pdf] ]]

\\ \\ \\ \\

Restore

May 09, 2012, at 11:53 AM EST by admin -

Changed line 56 from:

In [[http://rd.springer.com/article/10.1007/s00220-011-1363-1| ''Comm. in Math. Phys.]]; [[http://arxiv.org/abs/1009.3464|[arXiv] ]]

to:

In [[http://rd.springer.com/article/10.1007/s00220-011-1363-1| ''Comm. in Math. Phys.'']]; [[http://arxiv.org/abs/1009.3464|[arXiv] ]]

Restore

May 09, 2012, at 11:53 AM EST by admin -

Deleted lines 53-59:

~~\\ \\ \\ \\~~

Changed lines 56-63 from:

~~Submitted~~ [[http://~~arxiv~~.~~org~~/~~abs~~/~~1009~~.~~3464~~|~~[arXiv]~~ ]]

to:

In [[http://rd.springer.com/article/10.1007/s00220-011-1363-1| ''Comm. in Math. Phys.]]; [[http://arxiv.org/abs/1009.3464|[arXiv] ]]

\\ \\ \\ \\

Restore

May 09, 2012, at 12:53 AM EST by admin -

Added lines 43-46:

* Approximate Nash equilibria in perturbation resilient games \\
Nina Balcan, Mark Braverman \\
Working paper; [[http://arxiv.org/abs/1008.1827|[arXiv]]]

Deleted lines 59-61:

*Approximate Nash equilibria under stability conditions \\
Nina Balcan, Mark Braverman \\
Working paper [[http://arxiv.org/abs/1008.1827|[arXiv]]]

Restore

May 09, 2012, at 12:51 AM EST by admin -

Deleted lines 33-36:

*Pseudorandom Generators for Regular Branching Programs \\
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff \\
FOCS'10; [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=132399| [video by Anup] ]]

Added lines 42-53:

Restore

May 09, 2012, at 12:46 AM EST by admin -

Added lines 20-23:

* The Grothendieck constant is strictly smaller than Krivine's bound \\
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor \\
FOCS'11; [[http://arxiv.org/abs/1103.6161| [arXiv] ]]

Restore

May 09, 2012, at 12:40 AM EST by admin -

Added lines 36-39:

* Truthful mechanisms for competing submodular processes \\
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren \\
Preprint; [[http://arxiv.org/abs/1202.2097 | [arXiv] ]]

Restore

May 09, 2012, at 12:36 AM EST by admin -

Added lines 4-7:

* Towards deterministic tree code constructions\\
Mark Braverman \\
ITCS'12; [[http://eccc.hpi-web.de/report/2011/064/ | [ECCC] ]]

Restore

May 09, 2012, at 12:34 AM EST by admin -

Changed lines 6-7 from:

Mark Braverman, Alexander Grigo, Cristobal Rojas \\
ITCS'12; [[http://arxiv.org/abs/1201.0488 | [arXiv] ]]

to:

Mark Braverman, Alexander Grigo, Cristobal Rojas \\
ITCS'12; [[http://arxiv.org/abs/1201.0488 | [arXiv] ]]

Restore

May 09, 2012, at 12:33 AM EST by admin -

Restore

May 09, 2012, at 12:32 AM EST by admin -

Restore

May 09, 2012, at 12:32 AM EST by admin -

Added lines 4-7:

* Noise vs computational intractability in dynamics \\
Mark Braverman, Alexander Grigo, Cristobal Rojas \\
ITCS'12; [[http://arxiv.org/abs/1201.0488 | [arXiv] ]]

Restore

May 09, 2012, at 12:30 AM EST by admin -

Added lines 4-7:

* A discrepancy lower bound for information complexity \\
Mark Braverman, Omri Weinstein \\
Submitted; [[http://eccc.hpi-web.de/report/2011/164/ | [ECCC] ]]

Restore

May 09, 2012, at 12:29 AM EST by admin -

Changed lines 3-4 from:

!!! ~~Recent~~ publications

to:

!!! Selected recent publications

Changed line 22 from:

!!! ~~Less recent~~ publications

to:

!!! Other publications

Restore

May 09, 2012, at 12:28 AM EST by admin -

Added lines 4-7:

* Interactive information complexity \\
Mark Braverman \\
STOC'12; [[http://eccc.hpi-web.de/report/2011/123/| [ECCC] ]]

Restore

May 09, 2012, at 12:25 AM EST by admin -

Changed line 16 from:

FOCS'10; [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

to:

FOCS'10; [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=132399| [video by Anup] ]]

Restore

May 09, 2012, at 12:23 AM EST by admin -

Changed lines 14-17 from:

to:

*Pseudorandom Generators for Regular Branching Programs \\
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff \\
FOCS'10; [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

Changed lines 22-25 from:

*
*Pseudorandom Generators for Regular Branching Programs \\
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff \\
FOCS'10 [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

to:

Restore

May 09, 2012, at 12:23 AM EST by admin -

Changed line 6 from:

Mark Braverman ~~and~~ Anup Rao \\

to:

Mark Braverman, Anup Rao \\

Restore

May 09, 2012, at 12:23 AM EST by admin -

Deleted line 13:

~~http://arxiv.org/abs/1106.3595~~

Restore

May 09, 2012, at 12:22 AM EST by admin -

Changed lines 7-9 from:

STOC'11;
[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC] ]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| [video by Anup] ]]

to:

STOC'11; [[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC] ]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| [video by Anup] ]]

Changed lines 11-12 from:

FOCS'11;
[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC] ]]

to:

FOCS'11; [[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC] ]]

Restore

May 09, 2012, at 12:22 AM EST by admin -

Changed line 13 from:

[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

to:

[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC] ]]

Restore

May 09, 2012, at 12:22 AM EST by admin -

Changed line 7 from:

STOC'11 \\

to:

STOC'11;

Changed lines 12-13 from:

FOCS'11 [[Papers/amortizedcommunication.pdf|[pdf]]] \\
Earlier version (under a different title) [[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

to:

FOCS'11;
[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

Restore

May 09, 2012, at 12:21 AM EST by admin -

Changed line 12 from:

~~Submitted~~ [[Papers/amortizedcommunication.pdf|[pdf]]] \\

to:

FOCS'11 [[Papers/amortizedcommunication.pdf|[pdf]]] \\

Restore

May 09, 2012, at 12:21 AM EST by admin -

Deleted lines 9-12:

~~!!! Less recent publications~~

Added lines 15-22:

http://arxiv.org/abs/1106.3595

!!! Less recent publications

*

Restore

May 09, 2012, at 12:17 AM EST by admin -

Changed line 8 from:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| [video by Anup]]]

to:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC] ]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| [video by Anup] ]]

Restore

May 09, 2012, at 12:17 AM EST by admin -

Changed line 8 from:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| video by Anup]]

to:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| [video by Anup]]]

Restore

May 09, 2012, at 12:17 AM EST by admin -

Changed line 8 from:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]]

to:

[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]] [[http://research.microsoft.com/apps/video/default.aspx?id=147644| video by Anup]]

Restore

May 09, 2012, at 12:16 AM EST by admin -

Deleted lines 4-5:

~~!!! Less recent publications~~

Changed line 7 from:

~~Submitted~~ \\

to:

STOC'11 \\

Added lines 9-12:

!!! Less recent publications

Restore

May 08, 2012, at 10:07 PM EST by admin -

Changed lines 1-3 from:

(:title ~~Mark Braverman - All~~ Publications:)

!! ~~All~~ publications

to:

(:title Publications:)

!!! Recent publications

!!! Less recent publications

Restore

April 23, 2012, at 12:07 AM EST by admin -

Deleted line 4:

Changed line 70 from:

Computability of Brolin-Lyubich measure

to:

* Computability of Brolin-Lyubich measure

Changed line 74 from:

The rate of convergence of the Walk on Spheres Algorithm

to:

* The rate of convergence of the Walk on Spheres Algorithm

Changed line 78 from:

Thurston equivalence to a rational map is decidable

to:

* Thurston equivalence to a rational map is decidable

Changed line 82 from:

How to compress interactive communication

to:

* How to compress interactive communication

Changed line 87 from:

Phylogenetic Reconstruction with Insertions and Deletions

to:

* Phylogenetic Reconstruction with Insertions and Deletions

Changed line 91 from:

Monotonicity and Implementability

to:

* Monotonicity and Implementability

Changed line 95 from:

Sorting from Noisy Information

to:

* Sorting from Noisy Information

Changed line 99 from:

Ascending unit demand auctions with budget limits

to:

* Ascending unit demand auctions with budget limits

Changed line 103 from:

Position Auctions with Budgets: Existence and Uniqueness

to:

* Position Auctions with Budgets: Existence and Uniqueness

Changed line 107 from:

Poly-logarithmic independence fools AC0 circuits

to:

* Poly-logarithmic independence fools AC0 circuits

Changed line 112 from:

Finding low error clusterings

to:

* Finding low error clusterings

Changed line 116 from:

The complexity of simulating Brownian Motion

to:

* The complexity of simulating Brownian Motion

Changed line 120 from:

Constructing Locally Connected Non-Computable Julia Sets

to:

* Constructing Locally Connected Non-Computable Julia Sets

Changed line 124 from:

Space-Efficient Counting in Graphs on Surfaces

to:

* Space-Efficient Counting in Graphs on Surfaces

Changed line 128 from:

Branching Programs for Tree Evaluation

to:

* Branching Programs for Tree Evaluation

Changed line 135 from:

2004-2008

to:

!!! 2004-2008

Changed lines 137-142 from:

Book: Computability of Julia Sets
Mark Braverman, Michael Yampolsky
~~Springer, 2008~~
[~~Amazon~~] ~~[Springer]~~

Noisy Sorting Without Resampling

to:

*Book: Computability of Julia Sets\\
Mark Braverman, Michael Yampolsky\\
Springer, 2008
[Amazon] [Springer]

* Noisy Sorting Without Resampling

Changed line 146 from:

Mafia : A Theoretical Study of Players and Coalitions in a Partial Information Environment

to:

* Mafia : A Theoretical Study of Players and Coalitions in a Partial Information Environment

Changed line 150 from:

On ad hoc routing with guaranteed delivery

to:

* On ad hoc routing with guaranteed delivery

Changed line 154 from:

The complexity of properly learning simple concept classes

to:

* The complexity of properly learning simple concept classes

Changed line 158 from:

Computability of Julia Sets

to:

* Computability of Julia Sets

Changed line 162 from:

Derandomizing Euclidean random walks

to:

* Derandomizing Euclidean random walks

Changed line 166 from:

Constructing Non-Computable Julia Sets

to:

* Constructing Non-Computable Julia Sets

Changed line 170 from:

Parity Problems in Planar Graphs

to:

* Parity Problems in Planar Graphs

Changed line 174 from:

Filled Julia sets with empty interior are computable

to:

* Filled Julia sets with empty interior are computable

Changed line 178 from:

On computational complexity of Riemann mapping

to:

* On computational complexity of Riemann mapping

Changed line 182 from:

Termination of Integer Linear Programs

to:

* Termination of Integer Linear Programs

Changed lines 186-188 from:

Non-Computable Julia Sets
~~Mark Braverman, Michael~~ Yampolsky
Journ. Amer. Math. Soc. 19(3), 2006 [arXiv][bib]

to:

* Non-Computable Julia Sets\\
Mark Braverman, Michael Yampolsky\\
Journ. Amer. Math. Soc. 19(3), 2006 [arXiv][bib]

Changed lines 190-192 from:

Computing over the Reals: Foundations for Scientific Computing
~~Mark Braverman, Stephen~~ Cook
Notices of the AMS, 53(3), March 2006 [arXiv] [bib]

to:

* Computing over the Reals: Foundations for Scientific Computing\\
Mark Braverman, Stephen Cook\\
Notices of the AMS, 53(3), March 2006 [arXiv] [bib]

Changed lines 194-196 from:

Parabolic Julia Sets are Polynomial Time Computable
~~Mark~~ Braverman
Nonlinearity 19, 2006 [arXiv][bib]

to:

* Parabolic Julia Sets are Polynomial Time Computable\\
Mark Braverman\\
Nonlinearity 19, 2006 [arXiv][bib]

Changed lines 198-200 from:

On computational complexity of Siegel Julia sets
~~Ilia Binder~~, ~~Mark Braverman, Michael~~ Yampolsky
Commun. Math. Physics, 264(2), 2006 [arXiv] [bib]

to:

* On computational complexity of Siegel Julia sets\\
Ilia Binder, Mark Braverman, Michael Yampolsky\\
Commun. Math. Physics, 264(2), 2006 [arXiv] [bib]

Changed lines 202-205 from:

On the Complexity of Real Functions
~~Mark~~ Braverman
~~FOCS 2005~~ [~~pdf~~] ~~[bib]~~
Full version [arXiv]

to:

* On the Complexity of Real Functions\\
Mark Braverman\\
FOCS 2005 [pdf] [bib]\\
Full version [arXiv]

Changed lines 207-209 from:

Learnability and Automatizability
~~Misha Alekhnovich~~, ~~Mark Braverman~~, ~~Vitaly Feldman~~, ~~Adam Klivans, Toniann~~ Pitassi
FOCS 2004 [pdf] [bib]

to:

* Learnability and Automatizability\\
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi\\
FOCS 2004 [pdf] [bib]

Changed lines 211-215 from:

Hyperbolic Julia sets are poly-time computable
~~Mark~~ Braverman
~~CCA (Computability and Complexity in Analysis) 2004, ENTCS 120~~ [~~pdf~~] ~~[bib]~~

to:

* Hyperbolic Julia sets are poly-time computable\\
Mark Braverman\\
CCA (Computability and Complexity in Analysis) 2004, ENTCS 120 [pdf] [bib]

Changed line 218 from:

* Method of registering and aligning multiple ~~images~~

to:

* Method of registering and aligning multiple images\\

Restore

April 23, 2012, at 12:03 AM EST by admin -

Changed lines 217-222 from:

Other Manuscripts

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]

to:

!!!Other Manuscripts

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

Changed lines 224-226 from:

Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable
~~Mark~~ Braverman
M.Sc. Thesis [pdf]

to:

* Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable\\
Mark Braverman\\
M.Sc. Thesis [pdf]

Restore

April 23, 2012, at 12:01 AM EST by admin -

Changed lines 4-6 from:

~~!!! 2009+~~

to:

Changed line 24 from:

*Computability of Brolin-Lyubich measure\\

to:

* Computability of Brolin-Lyubich measure\\

Changed line 28 from:

*The rate of convergence of the Walk on Spheres Algorithm \\

to:

* The rate of convergence of the Walk on Spheres Algorithm \\

Changed line 34 from:

*Thurston equivalence to a rational map is decidable\\

to:

* Thurston equivalence to a rational map is decidable\\

Changed line 39 from:

*How to compress interactive communication\\

to:

* How to compress interactive communication\\

Changed lines 44-50 from:

Phylogenetic Reconstruction with Insertions and Deletions
~~[[People/AlexAndoni.html|Alex~~ Andoni]],
Mark Braverman,
~~[[People/AvinatanHassidim.html|Avinatan~~ Hassidim]]

(:cell class="papersubt":) Working paper

to:

* Phylogenetic Reconstruction with Insertions and Deletions\\
Alex Andoni, Mark Braverman, Avinatan Hassidim
Working paper

Changed lines 50-53 from:

Matching with couples revisited
~~Itai Ashalgi~~, ~~Mark Braverman, Avinatan~~ Hassidim
Working paper [pdf]

to:

* Matching with couples revisited\\
Itai Ashalgi, Mark Braverman, Avinatan Hassidim\\
Working paper [pdf]

Changed lines 54-56 from:

Towards coding for maximum errors in interactive communication
~~Mark Braverman, Anup~~ Rao
~~Submitted~~ [ECCC]

to:

Changed lines 63-66 from:

Information equals amortized communication
Mark Braverman, Anup Rao
submitted [pdf]
Earlier version (under a different title) [ECCC]

to:

* Pseudorandom Generators for Regular Branching Programs\\
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff\\
FOCS'10 [ECCC]

Changed lines 67-73 from:

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]

to:

* Approximate Nash equilibria under stability conditions\\
Nina Balcan, Mark Braverman\\
Working paper [arXiv]

Restore

April 22, 2012, at 05:55 PM EST by admin -

Deleted line 34:

Changed lines 55-177 from:

<tr> <td class="papert" colspan=3> Monotonicity and Implementability </tr>
[[People/ItaiAshlagi.html|Itai Ashalgi]], Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]],
[[People/DovMonderer.html|Dov Monderer]]

[[http://www.econometricsociety.org/|Econometrica]], forthcoming

(:cell align=left:) [[Papers/monotonicity-and-implementability.pdf|[pdf]]]

Sorting from Noisy Information </tr>
(:cell colspan=2 align=left:) Mark Braverman,
[[People/ElchananMossel.html|Elchanan Mossel]]
Submitted [[http://arxiv.org/abs/0910.1191|[arXiv]]] [[Bibs/Mossel09.html|[bib]]]

*Ascending unit demand auctions with budget limits </tr>
[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]]
Working paper
[[Papers/ud3.pdf|[pdf]]]

Position Auctions with Budgets: Existence and Uniqueness

[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]], [[People/RonLavi.html|Ron Lavi]],
[[People/MosheTennenholtz.html|Moshe Tennenholtz]]

(:cell class="papersubt":) [[http://www.bepress.com/bejte/|''The
B.E. Journal of Theoretical Economics'']]</span>'' ([[http://www.bepress.com/bejte/ratingsystem.html|Advances]]), '''10'''(1),
[[http://www.bepress.com/bejte/vol10/iss1/art20/| Article 20]], 2010
(:cell align=left:) [[Papers/pa-with-budgets.pdf|[pdf]]]

<tr> <td class="papert" colspan=3>Poly-logarithmic independence fools AC0 circuits </tr>
(:cell colspan=2 align=left:) Mark Braverman
(:cell class="papersubt":) Complexity 2009
(:cell align=left:) [[Papers/FoolAC0v7.pdf|[pdf]]] [[http://eccc.hpi-web.de/eccc-reports/2009/TR09-011/|[ECCC]]]
[[Bibs/Complexity09.html|[bib]]]
(:cell class="papersubt":) To appear in Journal of the ACM

<tr> <td class="papert" colspan=3> Finding low error clusterings </tr>
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman<td>
<td>

(:cell class="papersubt":) COLT 2009
(:cell align=left:) [[Papers/clusters09.pdf|[pdf]]] [[Bibs/Balcan09.html|[bib]]]

<tr> <td class="papert" colspan=3> The complexity of simulating Brownian Motion </tr>
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
(:cell class="papersubt":) SODA 2009
[[Papers/SimBM.pdf|[pdf]]] [[Bibs/SODA09.html|[bib]]]

<tr> <td class="papert" colspan=3> Constructing Locally Connected Non-Computable Julia Sets </tr>
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

(:cell class="papersubt":) Commun. Math. Physics, [[http://www.springerlink.com/content/ym0621v1n8266832/|291(2)]], 2009
(:cell align=left:) [[Papers/LocConn09.pdf|[pdf]]] [[Bibs/LocConn09.html|[bib]]]

<tr> <td class="papert" colspan=3> Space-Efficient Counting in Graphs on Surfaces </tr>
(:cell colspan=2 align=left:) Mark Braverman,
[[People/RaghavKulkarni.html|Raghav Kulkarni]],
[[People/SambuddhaRoy.html|Sambuddha Roy]]

(:cell class="papersubt":) Computational Complexity [[http://www.springerlink.com/content/l32x712w6194/?p=2479c469b866483a897565aa7b5ad611&pi=0| 18(4)]], 2009
(:cell align=left:) [[Papers/SurfCount.pdf|[pdf]]]
[[Bibs/SurfCount.html|[bib]]]

<tr> <td class="papert" colspan=3> Branching Programs for Tree Evaluation </tr>
(:cell colspan=2 align=left:) Mark Braverman,
[[People/StephenCook.html|Stephen Cook]],
[[People/PierreMcKenzie.html|Pierre McKenzie]], [[People/RahulSanthanam.html| Rahul Santhanam ]], Dustin Wehr

(:cell class="papersubt":) MFCS 2009
(:cell align=left:)[[Papers/MFCS09.pdf|[pdf]]] [[Bibs/MFCS09.html|[bib]]]
(:cell class="papersubt":) Full version
[[Papers/pebblesFull.pdf|[pdf]]]

(:cell class="papersubt":) Slides from Steve Cook's talk with a $100 prize offer
[[http://www.cs.utoronto.ca/~sacook/barriers.ps|[ps]]]

\\
!!! 2004-2008
(:table BORDER=0 width=70%:)
<td width="95">
[[http://www.springer.com/math/cse/book/978-3-540-68546-3|
<img src="Attach:bookcover.jpg"/>

(:cell valign="top":)
(:table BORDER=0 width=100%:)
<tr> <td>
(:cell class="papert" colspan=2:)
Book: Computability of Julia Sets
</tr>
(:cellnr:)
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]]]]

<tr> <td>&nbsp
(:cell class="papersubt":) Springer, 2008
(:cell align=left:)
(:cell:) </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[http://www.amazon.com/dp/3540685464|[Amazon]]] &nbsp
[[http://www.springer.com/math/cse/book/978-3-540-68546-3|[Springer]]]
</a>

(:tableend:)
(:tableend:)

\\
(:table BORDER=0 width=70%:)
(:cellnr class="papert" colspan=3:)

to:

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]

2004-2008

Book: Computability of Julia Sets
Mark Braverman, Michael Yampolsky
Springer, 2008
[Amazon] [Springer]

Changed lines 150-475 from:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/ElchananMossel.html|Elchanan Mossel]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) SODA 2008
(:cell align=left:) [[http://arxiv.org/abs/0707.1051|[arXiv]]]
[[Bibs/SODA08.html|[bib]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Mafia : A Theoretical Study of Players and Coalitions in a Partial
Information Environment </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/OmidEtesami.html|Omid Etesami]],
[[People/ElchananMossel.html|Elchanan Mossel]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Annals of Appl.
Prob. [[http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&page=toc&handle=euclid.aoap/1211819783|18(3)]],
2008
(:cell align=left:) [[http://www.arxiv.org/abs/math.PR/0609534|[arXiv]]]

[[Bibs/Mafia.html|[bib]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>On ad hoc routing with guaranteed delivery </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman
<td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Brief announcement, PODC 2008
(:cell align=left:) [[http://www.arxiv.org/abs/0804.0862|[arXiv]]][[Bibs/PODC08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> The complexity of properly learning simple concept classes </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/MishaAlekhnovich.html|Misha Alekhnovich]],
Mark Braverman,
[[People/VitalyFeldman.html|Vitaly Feldman]],
[[People/AdamKlivans.html|Adam Klivans]],
[[People/ToniannPitassi.html|Toniann Pitassi]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Journal of Computer and System Sciences, [[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4NK4GCV-5&_user=10&_coverDate=02%2F29%2F2008&_rdoc=4&_fmt=high&_orig=browse&_srch=doc-info(%23toc%236864%232008%23999259998%23671959%23FLP%23display%23Volume)&_cdi=6864&_sort=d&_docanchor=&view=c&_ct=11&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=6c7543fa92d8667f5fb4fdb999b3f1f4|74(1)]], 2008
(:cell align=left:) [[Papers/ABFKP_Proper_Hardness_08.pdf|[pdf]]] [[Bibs/ABFKP08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Computability of Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Moscow Math. Journal [[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mmj&paperid=311&option_lang=eng|8(2)]], 2008
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0610340|[arXiv]]][[Bibs/MMJ08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Derandomizing Euclidean random walks </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) RANDOM 2007
(:cell align=left:)
[[Papers/euclid.pdf|[pdf]]]
[[Bibs/RANDOM07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Constructing Non-Computable Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) STOC 2007
(:cell align=left:)

[[Papers/camstoc07.pdf|[pdf]]] [[Bibs/STOC07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Parity
Problems in Planar Graphs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,

[[People/RaghavKulkarni.html|Raghav Kulkarni]],
[[People/SambuddhaRoy.html|Sambuddha Roy]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Complexity 2007
(:cell align=left:)
[[Papers/PlanarDet.pdf|[pdf]]]
[[Bibs/Complexity07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Filled Julia sets with
empty interior are computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Journal of
Found. of Comp. Math. [[http://www.springerlink.com/content/w05m337381652123/|7(4)]],
2007
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0410580|[arXiv]]]
[[Bibs/FOCM07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On computational
complexity of Riemann mapping </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Arkiv for Matematik, [[http://www.springerlink.com/content/u10620n72u5u26x7/|45(2)]], 2007
(:cell align=left:) [[http://www.arxiv.org/abs/math.CV/0505617|[arXiv]]][[Bibs/Riemann07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Termination of Integer Linear Programs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) CAV (Computer-Aided Verification) 2006
(:cell align=left:) [[Papers/CAV2006.pdf|[pdf]]] [[Bibs/CAV06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Non-Computable Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,

[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Journ. Amer. Math. Soc.
[[http://www.ams.org/journals/jams/2006-19-03/|19(3)]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0406416|[arXiv]]][[Bibs/JAMS06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Computing over the Reals: Foundations
for Scientific Computing </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/StephenCook.html|Stephen Cook]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Notices of the
AMS, [[http://www.ams.org/notices/200603/200603-toc.html|53(3)]],
March 2006
(:cell align=left:) [[http://www.arxiv.org/abs/cs.CC/0509042|[arXiv]]]
[[Bibs/Notices06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Parabolic Julia Sets are Polynomial Time Computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Nonlinearity [[http://stacks.iop.org/Non/19/1383|19]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0505036|[arXiv]]][[Bibs/Nonlinearity06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On computational
complexity of Siegel Julia sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Commun. Math. Physics, [[http://www.springerlink.com/content/9046301604j78727/|264(2)]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0502354|[arXiv]]] [[Bibs/CMP06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On the Complexity of
Real Functions </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS 2005
(:cell align=left:) [[Papers/FOCS05.pdf|[pdf]]]
[[Bibs/FOCS05.html|[bib]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Full version
(:cell align=left:) [[http://www.arxiv.org/abs/cs.CC/0502066|[arXiv]]]
(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Learnability and
Automatizability </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/MishaAlekhnovich.html|Misha Alekhnovich]],
Mark Braverman,
[[People/VitalyFeldman.html|Vitaly Feldman]],
[[People/AdamKlivans.html|Adam Klivans]],

[[People/ToniannPitassi.html|Toniann Pitassi]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS 2004
(:cell align=left:) [[Papers/LearnAuto.pdf|[pdf]]] [[Bibs/FOCS04.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Hyperbolic Julia sets are poly-time
computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) CCA (Computability and Complexity in Analysis) 2004,
ENTCS [[http://www.sciencedirect.com/science?_ob=PublicationURL&_cdi=13109&_pubType=J&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=fe76401b8ce6ff05b31424fccb650eb2&jchunk=120#120|

120]]
(:cell align=left:) [[Papers/CCA04.pdf|[pdf]]] [[Bibs/CCA04.html|[bib]]]
(:cell:) </tr>
(:tableend:)

\\
\\
!!! Other Manuscripts
\\
(:table BORDER=0 width=70%:)
(:cellnr class="papert" colspan=3:)Method of registering and aligning multiple images
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic,
Vyacheslav Zavadsky

<tr> <td>&nbsp
(:cell colspan=2 align=left:) [[http://www.semiconductor.com/|Semiconductor Insights Inc.]]

</tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) US patent application 20060257051
(:cell align=left:) [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220060257051%22.PGNR.&OS=DN/20060257051&RS=DN/20060257051|[USPTO]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are
Poly-Time Computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) M.Sc. Thesis
(:cell align=left:) [[Papers/MarkThesis.pdf|[pdf]]]
(:cell:) </tr>
<tr><td colspan=4>&nbsp<td></tr>
(:tableend:)

!!!! [[Attach:index.htm| Back to main page ]]

\\
\\

to:

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]

Other Manuscripts

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

Restore

April 22, 2012, at 03:23 AM EST by admin -

Changed lines 46-49 from:

~~<tr> <td class="papert" colspan=3> Phylogenetic Reconstruction with Insertions and Deletions </tr>~~

to:

Phylogenetic Reconstruction with Insertions and Deletions

Changed lines 50-51 from:

~~<tr> <td>&nbsp&nbsp&nbsp~~

to:

Changed lines 57-60 from:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,

to:

[[People/ItaiAshlagi.html|Itai Ashalgi]], Mark Braverman,

Deleted lines 60-61:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Deleted lines 64-65:

~~<tr> <td class="papert" colspan=3>~~

Changed lines 68-73 from:

(:cell class="papersubt":) Submitted
(:cell align=left:) [[http://arxiv.org/abs/0910.1191|[arXiv]]] [[Bibs/Mossel09.html|[bib]]]

<tr> <td class="papert" colspan=3> Ascending unit demand auctions with budget limits </tr>

to:

Submitted [[http://arxiv.org/abs/0910.1191|[arXiv]]] [[Bibs/Mossel09.html|[bib]]]

*Ascending unit demand auctions with budget limits </tr>

Changed lines 77-79 from:

~~<tr> <td class="papert" colspan=3> Position Auctions with Budgets: Existence and Uniqueness </tr>~~

to:

Position Auctions with Budgets: Existence and Uniqueness

Deleted line 83:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Restore

April 22, 2012, at 03:21 AM EST by admin -

Changed lines 21-22 from:

*Approximate Nash equilibria under stability conditions
Nina Balcan, Mark ~~Braverman~~

to:

*Approximate Nash equilibria under stability conditions \\
Nina Balcan, Mark Braverman \\

Changed lines 25-30 from:

*Computability of Brolin-Lyubich measure
Ilia Binder, Mark Braverman, Cristobal Rojas, Michael Yampolsky
Submitted [[http://arxiv.org/abs/1009.3464|[arXiv]]]

*The rate of convergence of the Walk on Spheres Algorithm
Ilia Binder, Mark ~~Braverman~~

to:

*Computability of Brolin-Lyubich measure\\
Ilia Binder, Mark Braverman, Cristobal Rojas, Michael Yampolsky\\
Submitted [[http://arxiv.org/abs/1009.3464|[arXiv] ]]

*The rate of convergence of the Walk on Spheres Algorithm \\
Ilia Binder, Mark Braverman\\

Changed lines 33-37 from:

[[Papers/BBlocaldim.pdf|[pdf]]]</a>

*Thurston equivalence to a rational map is decidable
Sylvain Bonnot, Mark Braverman, Michael ~~Yampolsky~~

to:

[[Papers/BBlocaldim.pdf|[pdf]]]

*Thurston equivalence to a rational map is decidable\\
Sylvain Bonnot, Mark Braverman, Michael Yampolsky\\

Changed lines 41-45 from:

<tr> <td class="papert" colspan=3> How to compress interactive communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/BoazBarak.html|Boaz Barak]],

to:

*How to compress interactive communication\\
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao \\
STOC'10, invited to the special issue of SICOMP [[Papers/directsum.pdf|[pdf]]] \\
Previous version [[http://eccc.hpi-web.de/eccc-reports/2009/TR09-044/index.html|[ECCC]]]

<tr> <td class="papert" colspan=3> Phylogenetic Reconstruction with Insertions and Deletions </tr>

[[People/AlexAndoni.html|Alex Andoni]],

Changed lines 52-56 from:

[[People/~~XiChen~~.html|~~Xi Chen~~]],
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

to:

[[People/AvinatanHassidim.html|Avinatan Hassidim]]

Changed lines 55-67 from:

(:cell class="papersubt":) STOC'10, invited to the special issue of SICOMP
(:cell align=~~left:) [[Papers/directsum.pdf|[pdf]]]~~

~~(:cell:)~~ </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Previous version
(:cell align=left:) [[http://eccc.hpi-web.de/eccc-reports/2009/TR09-044/index.html|[ECCC]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Phylogenetic Reconstruction with Insertions and Deletions </tr>

to:

(:cell class="papersubt":) Working paper
(:cell align=left:) [[Papers/phylo-10.pdf|[pdf]]]

<tr> <td class="papert" colspan=3> Monotonicity and Implementability </tr>

Changed lines 62-63 from:

[[People/~~AlexAndoni~~.html|~~Alex Andoni~~]],

to:

[[People/ItaiAshlagi.html|Itai Ashalgi]],

Changed lines 64-66 from:

[[People/AvinatanHassidim.html|Avinatan Hassidim]]
<td>
<td>

to:

[[People/AvinatanHassidim.html|Avinatan Hassidim]],
[[People/DovMonderer.html|Dov Monderer]]

Deleted lines 68-87:

(:cell class="papersubt":) Working paper
(:cell align=left:) [[Papers/phylo-10.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Monotonicity and Implementability </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]],
[[People/DovMonderer.html|Dov Monderer]]

<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)

Changed lines 73-76 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted line 75:

~~(:cellnr:)&nbsp~~

Deleted line 78:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Changed lines 81-87 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted lines 83-84:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

Changed lines 86-91 from:

[[People/AvinatanHassidim.html|Avinatan Hassidim]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)

to:

[[People/AvinatanHassidim.html|Avinatan Hassidim]]

Added lines 88-96:

[[Papers/ud3.pdf|[pdf]]]

<tr> <td class="papert" colspan=3> Position Auctions with Budgets: Existence and Uniqueness </tr>

[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]], [[People/RonLavi.html|Ron Lavi]],
[[People/MosheTennenholtz.html|Moshe Tennenholtz]]

Deleted lines 97-112:

(:cell align=left:) [[Papers/ud3.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Position Auctions with Budgets: Existence and Uniqueness </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]], [[People/RonLavi.html|Ron Lavi]],
[[People/MosheTennenholtz.html|Moshe Tennenholtz]]
<td>
<td>

Deleted line 100:

Changed lines 104-109 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted line 108:

~~(:cellnr:)&nbsp~~

Deleted lines 109-112:

<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp

Deleted line 111:

Deleted lines 112-114:

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp

Changed lines 114-118 from:

(:cell align=left:)
(:cell:)
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted lines 115-116:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

Deleted line 118:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Changed lines 121-124 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted lines 123-125:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

Deleted lines 125-127:

<td>

<tr> <td>&nbsp&nbsp&nbsp

Deleted line 126:

~~(:cell align=left:)~~

Changed lines 128-130 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted lines 129-130:

(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

Deleted line 131:

~~<td>~~

Deleted lines 132-133:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Changed lines 135-137 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted line 136:

~~(:cellnr:)&nbsp~~

Deleted line 140:

~~<tr> <td>&nbsp&nbsp&nbsp~~

Changed lines 144-147 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

Deleted line 146:

~~(:cellnr:)&nbsp~~

Deleted line 147:

Changed lines 150-151 from:

~~<tr> <td>&nbsp&nbsp&nbsp~~

to:

Deleted lines 153-154:

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp

Deleted line 154:

~~(:cell align=left:)~~

Deleted lines 156-157:

(:cell:)
(:cellnr:)&nbsp&nbsp&nbsp

Deleted line 157:

~~(:cell align=left:)~~

Deleted lines 158-161:

(:cell:)
(:cellnr colspan=4:)&nbsp<td>
(:tableend:)

Restore

April 22, 2012, at 03:16 AM EST by admin -

Deleted lines 2-3:

Changed lines 15-19 from:

Earlier version (under a different title)
[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

to:

Earlier version (under a different title) [[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

Changed lines 21-63 from:

Approximate Nash equilibria under stability conditions
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Working paper
(:cell align=left:) [[http://arxiv.org/abs/1008.1827|[arXiv]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>
Computability of Brolin-Lyubich measure

</tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/CristobalRojas.html|Cristobal Rojas]],
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Submitted
[[http://arxiv.org/abs/1009.3464|[arXiv]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> The rate of convergence of the Walk on Spheres Algorithm </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) [[http://www.springer.com/birkhauser/mathematics/journal/39|

to:

*Approximate Nash equilibria under stability conditions
Nina Balcan, Mark Braverman
Working paper [[http://arxiv.org/abs/1008.1827|[arXiv]]]

*Computability of Brolin-Lyubich measure
Ilia Binder, Mark Braverman, Cristobal Rojas, Michael Yampolsky
Submitted [[http://arxiv.org/abs/1009.3464|[arXiv]]]

*The rate of convergence of the Walk on Spheres Algorithm
Ilia Binder, Mark Braverman
[[http://www.springer.com/birkhauser/mathematics/journal/39|

Deleted line 32:

~~(:cell align=left:)~~

Changed lines 34-55 from:

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>
Thurston equivalence to a rational map is decidable
</tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/~~SylvainBonnot~~.~~html~~|~~Sylvain Bonnot~~ ]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Preprint
[[http://arxiv.org/abs/1009.5713|[arXiv]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

to:

*Thurston equivalence to a rational map is decidable
Sylvain Bonnot, Mark Braverman, Michael Yampolsky
Preprint [[http://arxiv.org/abs/1009.5713|[arXiv]]]

Restore

April 22, 2012, at 03:12 AM EST by admin -

Changed lines 4-6 from:

\\
!! %block align="center"% All publications
\\

to:

!! All publications

Changed lines 7-70 from:

\\

<tr> <td class="papert" colspan=3> Towards coding for maximum errors in interactive communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Submitted
(:cell align=left:) [[http://www.eccc.uni-trier.de/report/2010/166/|[ECCC]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Information equals amortized communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) submitted
(:cell align=left:) [[Papers/amortizedcommunication.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Earlier version (under a different title)
(:cell align=left:) [[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Pseudorandom Generators for Regular Branching Programs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]],

[[People/RanRaz.html|Ran Raz]],
[[People/AmirYehudayoff.html|Amir Yehudayoff]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS'10
(:cell align=left:) [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Approximate Nash equilibria under stability conditions </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman<td>
<td>

to:

* Towards coding for maximum errors in interactive communication \\
Mark Braverman and Anup Rao \\
Submitted \\
[[http://www.eccc.uni-trier.de/report/2010/166/ | [ECCC]]]

* Information equals amortized communication \\
Mark Braverman, Anup Rao\\
Submitted [[Papers/amortizedcommunication.pdf|[pdf]]] \\
Earlier version (under a different title)
[[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

*Pseudorandom Generators for Regular Branching Programs \\
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff \\
FOCS'10 [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

Approximate Nash equilibria under stability conditions
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman

Restore

April 20, 2012, at 10:55 AM EST by admin -

Added lines 1-723:

(:title Mark Braverman - All Publications:)

\\
!! %block align="center"% All publications
\\
!!! 2009+
\\

<tr> <td class="papert" colspan=3> Towards coding for maximum errors in interactive communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Submitted
(:cell align=left:) [[http://www.eccc.uni-trier.de/report/2010/166/|[ECCC]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Information equals amortized communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) submitted
(:cell align=left:) [[Papers/amortizedcommunication.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Earlier version (under a different title)
(:cell align=left:) [[http://www.eccc.uni-trier.de/report/2010/083/|[ECCC]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Pseudorandom Generators for Regular Branching Programs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/AnupRao.html|Anup Rao]],

[[People/RanRaz.html|Ran Raz]],
[[People/AmirYehudayoff.html|Amir Yehudayoff]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS'10
(:cell align=left:) [[http://eccc.hpi-web.de/eccc-reports/2010/TR10-035/index.html|[ECCC]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Approximate Nash equilibria under stability conditions </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Working paper
(:cell align=left:) [[http://arxiv.org/abs/1008.1827|[arXiv]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>
Computability of Brolin-Lyubich measure

</tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/CristobalRojas.html|Cristobal Rojas]],
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Submitted
[[http://arxiv.org/abs/1009.3464|[arXiv]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> The rate of convergence of the Walk on Spheres Algorithm </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) [[http://www.springer.com/birkhauser/mathematics/journal/39|
Geometric and Functional Analysis]], accepted
(:cell align=left:)
[[Papers/BBlocaldim.pdf|[pdf]]]</a>
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>
Thurston equivalence to a rational map is decidable
</tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/SylvainBonnot.html|Sylvain Bonnot ]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Preprint
[[http://arxiv.org/abs/1009.5713|[arXiv]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> How to compress interactive communication </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/BoazBarak.html|Boaz Barak]],
Mark Braverman,
[[People/XiChen.html|Xi Chen]],
[[People/AnupRao.html|Anup Rao]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) STOC'10, invited to the special issue of SICOMP
(:cell align=left:) [[Papers/directsum.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Previous version
(:cell align=left:) [[http://eccc.hpi-web.de/eccc-reports/2009/TR09-044/index.html|[ECCC]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Phylogenetic Reconstruction with Insertions and Deletions </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/AlexAndoni.html|Alex Andoni]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Working paper
(:cell align=left:) [[Papers/phylo-10.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Monotonicity and Implementability </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]],
[[People/DovMonderer.html|Dov Monderer]]

<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)
[[http://www.econometricsociety.org/|Econometrica]], forthcoming

(:cell align=left:) [[Papers/monotonicity-and-implementability.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>
Sorting from Noisy Information </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/ElchananMossel.html|Elchanan Mossel]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Submitted
(:cell align=left:) [[http://arxiv.org/abs/0910.1191|[arXiv]]] [[Bibs/Mossel09.html|[bib]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Ascending unit demand auctions with budget limits </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)
Working paper

(:cell align=left:) [[Papers/ud3.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Position Auctions with Budgets: Existence and Uniqueness </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/ItaiAshlagi.html|Itai Ashalgi]],
Mark Braverman,
[[People/AvinatanHassidim.html|Avinatan Hassidim]], [[People/RonLavi.html|Ron Lavi]],
[[People/MosheTennenholtz.html|Moshe Tennenholtz]]
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) [[http://www.bepress.com/bejte/|''The
B.E. Journal of Theoretical Economics'']]</span>'' ([[http://www.bepress.com/bejte/ratingsystem.html|Advances]]), '''10'''(1),

[[http://www.bepress.com/bejte/vol10/iss1/art20/| Article 20]], 2010
(:cell align=left:) [[Papers/pa-with-budgets.pdf|[pdf]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Poly-logarithmic independence fools AC0 circuits </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman
<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Complexity 2009
(:cell align=left:) [[Papers/FoolAC0v7.pdf|[pdf]]] [[http://eccc.hpi-web.de/eccc-reports/2009/TR09-011/|[ECCC]]]

[[Bibs/Complexity09.html|[bib]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) To appear in Journal of the ACM
(:cell align=left:)
(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Finding low error clusterings </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/NinaBalcan.html|Nina Balcan]], Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) COLT 2009
(:cell align=left:) [[Papers/clusters09.pdf|[pdf]]] [[Bibs/Balcan09.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> The complexity of simulating Brownian Motion </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) SODA 2009
(:cell align=left:)
[[Papers/SimBM.pdf|[pdf]]] [[Bibs/SODA09.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Constructing Locally Connected Non-Computable Julia Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Commun. Math. Physics, [[http://www.springerlink.com/content/ym0621v1n8266832/|291(2)]], 2009
(:cell align=left:) [[Papers/LocConn09.pdf|[pdf]]] [[Bibs/LocConn09.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Space-Efficient Counting in Graphs on Surfaces </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/RaghavKulkarni.html|Raghav Kulkarni]],
[[People/SambuddhaRoy.html|Sambuddha Roy]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Computational Complexity [[http://www.springerlink.com/content/l32x712w6194/?p=2479c469b866483a897565aa7b5ad611&pi=0| 18(4)]], 2009
(:cell align=left:) [[Papers/SurfCount.pdf|[pdf]]]
[[Bibs/SurfCount.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Branching Programs for Tree Evaluation </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,

[[People/StephenCook.html|Stephen Cook]],
[[People/PierreMcKenzie.html|Pierre McKenzie]], [[People/RahulSanthanam.html| Rahul Santhanam ]], Dustin Wehr

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) MFCS 2009
(:cell align=left:)[[Papers/MFCS09.pdf|[pdf]]] [[Bibs/MFCS09.html|[bib]]]
(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Full version
(:cell align=left:)
[[Papers/pebblesFull.pdf|[pdf]]]

(:cell:)
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Slides from Steve Cook's talk with a $100 prize offer
(:cell align=left:)
[[http://www.cs.utoronto.ca/~sacook/barriers.ps|[ps]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>
(:tableend:)

\\
!!! 2004-2008
(:table BORDER=0 width=70%:)
<td width="95">
[[http://www.springer.com/math/cse/book/978-3-540-68546-3|
<img src="Attach:bookcover.jpg"/>

(:cell valign="top":)
(:table BORDER=0 width=100%:)
<tr> <td>
(:cell class="papert" colspan=2:)
Book: Computability of Julia Sets
</tr>
(:cellnr:)
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]]]]

<tr> <td>&nbsp
(:cell class="papersubt":) Springer, 2008
(:cell align=left:)
(:cell:) </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[http://www.amazon.com/dp/3540685464|[Amazon]]] &nbsp
[[http://www.springer.com/math/cse/book/978-3-540-68546-3|[Springer]]]
</a>

(:tableend:)
(:tableend:)

\\
(:table BORDER=0 width=70%:)
(:cellnr class="papert" colspan=3:)
Noisy Sorting Without Resampling

(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/ElchananMossel.html|Elchanan Mossel]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) SODA 2008
(:cell align=left:) [[http://arxiv.org/abs/0707.1051|[arXiv]]]
[[Bibs/SODA08.html|[bib]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Mafia : A Theoretical Study of Players and Coalitions in a Partial
Information Environment </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/OmidEtesami.html|Omid Etesami]],
[[People/ElchananMossel.html|Elchanan Mossel]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Annals of Appl.
Prob. [[http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&page=toc&handle=euclid.aoap/1211819783|18(3)]],
2008
(:cell align=left:) [[http://www.arxiv.org/abs/math.PR/0609534|[arXiv]]]

[[Bibs/Mafia.html|[bib]]]

(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>On ad hoc routing with guaranteed delivery </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman
<td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Brief announcement, PODC 2008
(:cell align=left:) [[http://www.arxiv.org/abs/0804.0862|[arXiv]]][[Bibs/PODC08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> The complexity of properly learning simple concept classes </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/MishaAlekhnovich.html|Misha Alekhnovich]],
Mark Braverman,
[[People/VitalyFeldman.html|Vitaly Feldman]],
[[People/AdamKlivans.html|Adam Klivans]],
[[People/ToniannPitassi.html|Toniann Pitassi]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Journal of Computer and System Sciences, [[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4NK4GCV-5&_user=10&_coverDate=02%2F29%2F2008&_rdoc=4&_fmt=high&_orig=browse&_srch=doc-info(%23toc%236864%232008%23999259998%23671959%23FLP%23display%23Volume)&_cdi=6864&_sort=d&_docanchor=&view=c&_ct=11&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=6c7543fa92d8667f5fb4fdb999b3f1f4|74(1)]], 2008
(:cell align=left:) [[Papers/ABFKP_Proper_Hardness_08.pdf|[pdf]]] [[Bibs/ABFKP08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Computability of Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Moscow Math. Journal [[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mmj&paperid=311&option_lang=eng|8(2)]], 2008
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0610340|[arXiv]]][[Bibs/MMJ08.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Derandomizing Euclidean random walks </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman<td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) RANDOM 2007
(:cell align=left:)
[[Papers/euclid.pdf|[pdf]]]
[[Bibs/RANDOM07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Constructing Non-Computable Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) STOC 2007
(:cell align=left:)

[[Papers/camstoc07.pdf|[pdf]]] [[Bibs/STOC07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Parity
Problems in Planar Graphs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,

[[People/RaghavKulkarni.html|Raghav Kulkarni]],
[[People/SambuddhaRoy.html|Sambuddha Roy]]

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Complexity 2007
(:cell align=left:)
[[Papers/PlanarDet.pdf|[pdf]]]
[[Bibs/Complexity07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Filled Julia sets with
empty interior are computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":)Journal of
Found. of Comp. Math. [[http://www.springerlink.com/content/w05m337381652123/|7(4)]],
2007
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0410580|[arXiv]]]
[[Bibs/FOCM07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On computational
complexity of Riemann mapping </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>

<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Arkiv for Matematik, [[http://www.springerlink.com/content/u10620n72u5u26x7/|45(2)]], 2007
(:cell align=left:) [[http://www.arxiv.org/abs/math.CV/0505617|[arXiv]]][[Bibs/Riemann07.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Termination of Integer Linear Programs </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) CAV (Computer-Aided Verification) 2006
(:cell align=left:) [[Papers/CAV2006.pdf|[pdf]]] [[Bibs/CAV06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3>Non-Computable Julia
Sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,

[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Journ. Amer. Math. Soc.
[[http://www.ams.org/journals/jams/2006-19-03/|19(3)]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0406416|[arXiv]]][[Bibs/JAMS06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Computing over the Reals: Foundations
for Scientific Computing </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman,
[[People/StephenCook.html|Stephen Cook]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Notices of the
AMS, [[http://www.ams.org/notices/200603/200603-toc.html|53(3)]],
March 2006
(:cell align=left:) [[http://www.arxiv.org/abs/cs.CC/0509042|[arXiv]]]
[[Bibs/Notices06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Parabolic Julia Sets are Polynomial Time Computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Nonlinearity [[http://stacks.iop.org/Non/19/1383|19]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0505036|[arXiv]]][[Bibs/Nonlinearity06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On computational
complexity of Siegel Julia sets </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)

[[People/IliaBinder.html|Ilia Binder]],
Mark Braverman,
[[People/MichaelYampolsky.html|Michael Yampolsky]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) Commun. Math. Physics, [[http://www.springerlink.com/content/9046301604j78727/|264(2)]], 2006
(:cell align=left:) [[http://www.arxiv.org/abs/math.DS/0502354|[arXiv]]] [[Bibs/CMP06.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> On the Complexity of
Real Functions </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS 2005
(:cell align=left:) [[Papers/FOCS05.pdf|[pdf]]]
[[Bibs/FOCS05.html|[bib]]]

(:cell:) </tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) Full version
(:cell align=left:) [[http://www.arxiv.org/abs/cs.CC/0502066|[arXiv]]]
(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Learnability and
Automatizability </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:)
[[People/MishaAlekhnovich.html|Misha Alekhnovich]],
Mark Braverman,
[[People/VitalyFeldman.html|Vitaly Feldman]],
[[People/AdamKlivans.html|Adam Klivans]],

[[People/ToniannPitassi.html|Toniann Pitassi]] <td>
<td>

<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) FOCS 2004
(:cell align=left:) [[Papers/LearnAuto.pdf|[pdf]]] [[Bibs/FOCS04.html|[bib]]]
(:cell:) </tr>
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Hyperbolic Julia sets are poly-time
computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) CCA (Computability and Complexity in Analysis) 2004,
ENTCS [[http://www.sciencedirect.com/science?_ob=PublicationURL&_cdi=13109&_pubType=J&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=fe76401b8ce6ff05b31424fccb650eb2&jchunk=120#120|

120]]
(:cell align=left:) [[Papers/CCA04.pdf|[pdf]]] [[Bibs/CCA04.html|[bib]]]
(:cell:) </tr>
(:tableend:)

\\
\\
!!! Other Manuscripts
\\
(:table BORDER=0 width=70%:)
(:cellnr class="papert" colspan=3:)Method of registering and aligning multiple images
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic,
Vyacheslav Zavadsky

<tr> <td>&nbsp
(:cell colspan=2 align=left:) [[http://www.semiconductor.com/|Semiconductor Insights Inc.]]

</tr>
(:cellnr:)&nbsp&nbsp&nbsp
(:cell class="papersubt":) US patent application 20060257051
(:cell align=left:) [[http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220060257051%22.PGNR.&OS=DN/20060257051&RS=DN/20060257051|[USPTO]]]

(:cell:)
(:cellnr colspan=4:)&nbsp<td>

<tr> <td class="papert" colspan=3> Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are
Poly-Time Computable </tr>
(:cellnr:)&nbsp
(:cell colspan=2 align=left:) Mark Braverman <td>
<tr> <td>&nbsp&nbsp&nbsp
(:cell class="papersubt":) M.Sc. Thesis
(:cell align=left:) [[Papers/MarkThesis.pdf|[pdf]]]
(:cell:) </tr>
<tr><td colspan=4>&nbsp<td></tr>
(:tableend:)

!!!! [[Attach:index.htm| Back to main page ]]

\\
\\

Restore