Mark Braverman

  • Source: Scopus
  • Calculated based on no. of publications stored in Pure and citations from Scopus
20042021

Research activity per year

If you made any changes in Pure these will be visible here soon.
Filter
Conference contribution

Search results

  • 2005

    On the complexity of real functions

    Braverman, M., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 155-164 10 p. 1530710. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    31 Scopus citations
  • 2006

    Termination of integer linear programs

    Braverman, M., Jan 1 2006, Computer Aided Verification - 18th International Conference, CAV 2006, Proceedings. Springer Verlag, p. 372-385 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4144 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    85 Scopus citations
  • 2007

    Constructing non-computable Julia sets

    Braverman, M. & Yampolsky, M., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 709-716 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    10 Scopus citations
  • Derandomization of euclidean random walks

    Binder, I. & Braverman, M., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 353-365 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    7 Scopus citations
  • Parity problems in planar graphs

    Braverman, M., Kulkarni, R. & Roy, S., Oct 2 2007, Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007. p. 222-235 14 p. 4262766. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    8 Scopus citations
  • 2008

    Brief announcement: On ad hoc routing with guaranteed delivery

    Braverman, M., Dec 17 2008, PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. 1 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • Noisy sorting without resampling

    Braverman, M. & Mossel, E., Dec 1 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 268-276 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    102 Scopus citations
  • 2009

    Branching programs for tree evaluation

    Braverman, M., Cook, S., McKenzie, P., Santhanam, R. & Wehr, D., 2009, Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings. p. 175-186 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5734 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • Computability and complexity of Julia sets (invited talk)

    Braverman, M., Nov 2009, Proceedings of the 6th International Conference on Computability and Complexity in Analysis, CCA 2009. Bauer, A., Hertling, P. & Ko, K-I. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 1 p. (OpenAccess Series in Informatics; vol. 11).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Fractional pebbling and thrifty branching programs

    Braverman, M., Cook, S., McKenzie, P., Santhanam, R. & Wehr, D., Dec 1 2009, Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings. p. 109-120 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 4).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • Poly-logarithmic independence fools AC0 circuits

    Braverman, M., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 3-8 6 p. 5231177. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    23 Scopus citations
  • The complexity of simulating Brownian Motion

    Binder, I. & Braverman, M., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 58-67 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    3 Scopus citations
  • 2010

    How to compress interactive communication

    Barak, B., Braverman, M., Chen, X. & Rao, A., Jul 23 2010, STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing. p. 67-76 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    96 Scopus citations
  • Pseudorandom generators for regular branching programs

    Braverman, M., Rao, A., Raz, R. & Yehudayoff, A., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 40-47 8 p. 5670950. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    32 Scopus citations
  • 2011

    Inapproximability of NP-complete variants of Nash equilibrium

    Austrin, P., Braverman, M. & Chlamtáč, E., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 13-25 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • Information equals amortized communication

    Braverman, M. & Rao, A., Dec 1 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 748-757 10 p. 6108245. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    93 Scopus citations
  • Matching with couples revisited

    Ashlagi, I., Braverman, M. & Hassidim, A., 2011, EC'11 - Proceedings of the 12th ACM Conference on Electronic Commerce. p. 335 1 p. (Proceedings of the ACM Conference on Electronic Commerce).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    5 Scopus citations
  • The Grothendieck constant is strictly smaller than Krivine's bound

    Braverman, M., Makarychev, K., Makarychev, Y. & Naor, A., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 453-462 10 p. 6108206. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    22 Scopus citations
  • Towards coding for maximum errors in interactive communication

    Braverman, M. & Rao, A., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. p. 159-166 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    60 Scopus citations
  • 2012

    A discrepancy lower bound for information complexity

    Braverman, M. & Weinstein, O., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 459-470 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    21 Scopus citations
  • Coding for interactive computation: Progress and challenges

    Braverman, M., Dec 1 2012, 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012. p. 1914-1921 8 p. 6483456

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    20 Scopus citations
  • Interactive information complexity

    Braverman, M., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 505-524 20 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    71 Scopus citations
  • Noise vs computational intractability in dynamics

    Braverman, M., Grigo, A. & Rojas, C., Feb 6 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 128-141 14 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    7 Scopus citations
  • Towards deterministic tree code constructions

    Braverman, M., Feb 6 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 161-167 7 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    45 Scopus citations
  • 2013

    A hard-to-compress interactive task?

    Braverman, M., Jan 1 2013, 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013. IEEE Computer Society, p. 8-12 5 p. 6736498. (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    9 Scopus citations
  • An information complexity approach to extended formulations

    Braverman, M. & Moitra, A., Jul 11 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 161-170 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    51 Scopus citations
  • A tight bound for set disjointness in the message-passing model

    Braverman, M., Ellen, F., Oshman, R., Pitassi, T. & Vaikuntanathan, V., Dec 1 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 668-677 10 p. 6686203. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    47 Scopus citations
  • Direct products in communication complexity

    Braverman, M., Weinstein, O., Rao, A. & Yehudayoff, A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 746-755 10 p. 6686211. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    34 Scopus citations
  • Direct product via round-preserving compression

    Braverman, M., Rao, A., Weinstein, O. & Yehudayoff, A., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 232-243 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    14 Scopus citations
  • Finding endogenously formed communities

    Balcan, M. F., Borgs, C., Braverman, M., Chayes, J. & Teng, S. H., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, p. 767-783 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    16 Scopus citations
  • From information to exact communication

    Braverman, M., Garg, A., Pankratov, D. & Weinstein, O., Jul 11 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 151-160 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    52 Scopus citations
  • Information lower bounds via self-reducibility

    Braverman, M., Garg, A., Pankratov, D. & Weinstein, O., 2013, Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Springer Verlag, p. 183-194 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7913 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    10 Scopus citations
  • Noise versus computational intractability in dynamics

    Braverman, M., Jul 26 2013, The Nature of Computation: Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Proceedings. 1 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7921 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • On the convergence of the Hegselmann-Krause system

    Bhattacharyya, A., Braverman, M., Chazelle, B. & Nguyen, H. L., Feb 11 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 61-65 5 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    40 Scopus citations
  • Search using queries on indistinguishable items

    Braverman, M. & Oshri, G., Dec 1 2013, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. p. 610-621 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 20).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Strategyproof mechanisms for competitive influence in networks

    Borodin, A., Braverman, M., Lucier, B. & Oren, J., 2013, WWW 2013 - Proceedings of the 22nd International Conference on World Wide Web. Association for Computing Machinery, p. 141-151 11 p. (WWW 2013 - Proceedings of the 22nd International Conference on World Wide Web).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    13 Scopus citations
  • 2014

    Interactive information and coding theory

    Braverman, M., 2014, Invited Lectures. Jang, S. Y., Kim, Y. R., Lee, D-W., Yie, I., Kim, Y. R., Lee, D-W. & Yie, I. (eds.). KYUNG MOON SA Co. Ltd., p. 535-559 25 p. (Proceeding of the International Congress of Mathematicans, ICM 2014; vol. 4).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Scopus citations
  • List and unique coding for interactive communication in the presence of adversarial noise

    Braverman, M. & Efremenko, K., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 236-245 10 p. 6979008. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    33 Scopus citations
  • Public vs private coin in bounded-round information

    Braverman, M. & Garg, A., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 502-513 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    21 Scopus citations
  • The computational hardness of pricing compound options

    Braverman, M. & Pasricha, K., 2014, ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 103-104 2 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Scopus citations
  • 2015

    An interactive information odometer and applications

    Braverman, M. & Weinstein, O., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 341-350 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    15 Scopus citations
  • Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis

    Braverman, M., Ko, Y. K. & Weinstein, O., Jan 1 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 970-982 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis

    Braverman, M., Ko, Y. K. & Weinstein, O., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 970-982 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    27 Scopus citations
  • Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

    Braverman, M., Garg, A., Ko, Y. K., Mao, J. & Touchette, D., Dec 11 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 773-791 19 p. 7354427. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    10 Scopus citations
  • On information complexity in the broadcast model

    Braverman, M. & Oshman, R., Jul 21 2015, PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 355-364 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. 2015-July).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    12 Scopus citations
  • Simulating noisy channel interaction [extended abstract]

    Braverman, M. & Mao, J., Jan 11 2015, ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science. Association for Computing Machinery, Inc, p. 21-30 10 p. (ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Scopus citations
  • Small value parallel repetition for general games

    Braverman, M. & Garg, A., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 335-340 6 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    12 Scopus citations
  • 2016

    Coding for interactive communication correcting insertions and deletions

    Braverman, M., Gelles, R., Mao, J. & Ostrovsky, R., Aug 1 2016, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Rabani, Y., Chatzigiannakis, I., Sangiorgi, D. & Mitzenmacher, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 61. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 55).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    8 Scopus citations
  • Communication lower bounds for statistical estimation problems via a distributed data processing inequality?

    Braverman, M., Garg, A., Ma, T., Nguyen, H. L. & Woodruff, D. P., Jun 19 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 1011-1020 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    39 Scopus citations
  • Constant-rate coding for multiparty interactive communication is impossible

    Braverman, M., Efremenko, K., Gelles, R. & Haeupler, B., Jun 19 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 999-1010 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    12 Scopus citations