☰

Mark Braverman - Publications

Affiliations: 
Computer Science Princeton University, Princeton, NJ 
Area:
Complexity theory, algorithms, game theory, machine learning, and applications of computer science in healthcare and medicine.
Tree Info Similar researchers PubMed Report error

43 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Braverman M, Juba B. The Price of Uncertain Priors in Source Coding Ieee Transactions On Information Theory. 65: 1165-1171. DOI: 10.1109/Tit.2018.2888475  0.333
2019 Braverman M. Information complexity and applications Japanese Journal of Mathematics. 14: 27-65. DOI: 10.1007/S11537-018-1727-9  0.313
2019 Alon N, Braverman M, Efremenko K, Gelles R, Haeupler B. Reliable communication over highly connected noisy networks Distributed Computing. 32: 505-515. DOI: 10.1007/S00446-017-0303-5  0.333
2017 Braverman M, Efremenko K, Gelles R, Haeupler B. Constant-Rate Coding for Multiparty Interactive Communication Is Impossible Journal of the Acm. 65: 1-41. DOI: 10.1145/3050218  0.344
2017 Braverman M, Gelles R, Mao J, Ostrovsky R. Coding for Interactive Communication Correcting Insertions and Deletions Ieee Transactions On Information Theory. 63: 6256-6270. DOI: 10.1109/Tit.2017.2734881  0.308
2016 Braverman M, Woodruff DP. Guest Editorial for Information Complexity and Applications Algorithmica. 76: 595-596. DOI: 10.1007/S00453-016-0180-5  0.418
2015 Braverman M, Schneider J, Rojas C. Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems. Physical Review Letters. 115: 098701. PMID 26371687 DOI: 10.1103/Physrevlett.115.098701  0.305
2015 Braverman M, Oshman R. On information complexity in the broadcast model Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 2015: 355-364. DOI: 10.1145/2767386.2767425  0.301
2015 Braverman M, Weinstein O. An interactive information odometer and applications Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 341-350. DOI: 10.1145/2746539.2746548  0.583
2015 Braverman M, Garg A, Ko YK, Mao J, Touchette D. Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2015: 773-791. DOI: 10.1137/16M1061400  0.39
2015 Braverman M, Weinstein O. A Discrepancy Lower Bound for Information Complexity Algorithmica. 1-19. DOI: 10.1007/S00453-015-0093-8  0.678
2015 Braverman M, Garg A, Pankratov D, Weinstein O. Information Lower Bounds via Self-Reducibility Theory of Computing Systems. DOI: 10.1007/S00224-015-9655-Z  0.663
2015 Braverman M, Ko YK, Weinstein O. Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 2015: 970-982.  0.609
2014 Braverman M, Efremenko K. List and unique coding for interactive communication in the presence of adversarial noise Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 236-245. DOI: 10.1137/141002001  0.333
2014 Braverman M, Rao A, Raz R, Yehudayoff A. Pseudorandom generators for regular branching programs Siam Journal On Computing. 43: 973-986. DOI: 10.1137/120875673  0.309
2014 Braverman M, Rao A. Toward coding for maximum errors in interactive communication Ieee Transactions On Information Theory. 60: 7248-7255. DOI: 10.1109/Tit.2014.2353994  0.316
2014 Braverman M, Rao A. Information equals amortized communication Ieee Transactions On Information Theory. 60: 6058-6069. DOI: 10.1109/Tit.2014.2347282  0.414
2013 Braverman M. Computing with real numbers, from archimedes to turing and beyond Communications of the Acm. 56: 74-83. DOI: 10.1145/2500890  0.315
2013 Braverman M, Moitra A. An information complexity approach to extended formulations Proceedings of the Annual Acm Symposium On Theory of Computing. 161-170. DOI: 10.1145/2488608.2488629  0.331
2013 Braverman M, Garg A, Pankratov D, Weinstein O. From information to exact communication Proceedings of the Annual Acm Symposium On Theory of Computing. 151-160. DOI: 10.1145/2488608.2488628  0.665
2013 Balcan MF, Braverman M, Spielman DA. Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009) Siam Journal On Computing. 42: 2286-2286. DOI: 10.1137/130973545  0.3
2013 Barak B, Braverman M, Chen X, Rao A. How to compress interactive communication Siam Journal On Computing. 42: 1327-1363. DOI: 10.1137/100811969  0.42
2013 Braverman M, Weinstein O, Rao A, Yehudayoff A. Direct products in communication complexity Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 746-755. DOI: 10.1109/FOCS.2013.85  0.627
2013 Braverman M, Ellen F, Oshman R, Pitassi T, Vaikuntanathan V. A tight bound for set disjointness in the message-passing model Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 668-677. DOI: 10.1109/FOCS.2013.77  0.31
2013 Braverman M, Rao A, Weinstein O, Yehudayoff A. Direct product via round-preserving compression Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7965: 232-243. DOI: 10.1007/978-3-642-39206-1_20  0.627
2012 Cook S, McKenzie P, Wehr D, Braverman M, Santhanam R. Pebbles and branching programs for tree evaluation Acm Transactions On Computation Theory. 3. DOI: 10.1145/2077336.2077337  0.513
2012 Braverman M. Interactive information complexity Proceedings of the Annual Acm Symposium On Theory of Computing. 505-524. DOI: 10.1137/17M1139254  0.391
2011 Austrin P, Braverman M, Chlamtáč E. Inapproximability of NP-complete variants of Nash equilibrium Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 13-25. DOI: 10.4086/Toc.2013.V009A003  0.33
2011 Braverman M, Makarychev K, Makarychev Y, Naor A. The Grothendieck constant is strictly smaller than Krivine's bound Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 453-462. DOI: 10.1017/Fmp.2013.4  0.316
2011 Binder I, Braverman M, Rojas C, Yampolsky M. Computability of Brolin-Lyubich Measure Communications in Mathematical Physics. 308: 743-771. DOI: 10.1007/S00220-011-1363-1  0.304
2009 Braverman M, Cook S, McKenzie P, Santhanam R, Wehr D. Fractional pebbling and thrifty branching programs Leibniz International Proceedings in Informatics, Lipics. 4: 109-120. DOI: 10.4230/LIPIcs.FSTTCS.2009.2311  0.398
2009 Braverman M, Yampolsky M. Constructing locally connected non-computable Julia sets Communications in Mathematical Physics. 291: 513-532. DOI: 10.1007/S00220-009-0858-5  0.325
2009 Braverman M, Kulkarni R, Roy S. Space-Efficient counting in graphs on surfaces Computational Complexity. 18: 601-649. DOI: 10.1007/S00037-009-0266-4  0.304
2009 Braverman M, Cook S, McKenzie P, Santhanam R, Wehr D. Branching programs for tree evaluation Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5734: 175-186. DOI: 10.1007/978-3-642-03816-7_16  0.458
2008 Braverman M, Etesami O, Mossel E. Mafia: A theoretical study of players and coalitions in a partial information environment Annals of Applied Probability. 18: 825-846. DOI: 10.1214/07-Aap456  0.307
2008 Alekhnovich M, Braverman M, Feldman V, Klivans AR, Pitassi T. The complexity of properly learning simple concept classes Journal of Computer and System Sciences. 74: 16-34. DOI: 10.1016/J.Jcss.2007.04.011  0.307
2007 Binder I, Braverman M, Yampolsky M. On the computational complexity of the Riemann mapping Arkiv For Matematik. 45: 221-239. DOI: 10.1007/S11512-007-0045-X  0.35
2007 Binder I, Braverman M, Yampolsky M. Filled Julia sets with empty interior are computable Foundations of Computational Mathematics. 7: 405-416. DOI: 10.1007/S10208-005-0210-1  0.324
2006 Braverman M, Yampolsky M. Non-computable Julia sets Journal of the American Mathematical Society. 19: 551-578. DOI: 10.1090/S0894-0347-05-00516-3  0.363
2006 Braverman M. Parabolic Julia sets are polynomial time computable Nonlinearity. 19: 1383-1401. DOI: 10.1088/0951-7715/19/6/009  0.345
2006 Binder I, Braverman M, Yampolsky M. On computational complexity of Siegel Julia sets Communications in Mathematical Physics. 264: 317-334. DOI: 10.1007/S00220-006-1546-3  0.384
2006 Braverman M, Cook S. Computing over the reals: Foundations for scientific computing Notices of the American Mathematical Society. 53: 318-329.  0.444
2005 Braverman M. Hyperbolic Julia sets are poly-time computable Electronic Notes in Theoretical Computer Science. 120: 17-30. DOI: 10.1016/J.Entcs.2004.06.031  0.402
Show low-probability matches.