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

  • A candidate for a strong separation of information and communication

    Braverman, M., Ganor, A., Kol, G. & Raz, R., Jan 1 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).

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

    3 Scopus citations
  • 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
  • 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
  • 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
  • A rounds vs. communication tradeoff for multi-party set disjointness

    Braverman, M. & Oshman, R., Nov 10 2017, Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017. IEEE Computer Society, p. 144-155 12 p. 8104054. (Annual Symposium on Foundations of Computer Science - Proceedings; vol. 2017-October).

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

    7 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
  • BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time

    Chen, X., Landau-Feibish, S., Braverman, M. & Rexford, J., Jul 30 2020, SIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication. Association for Computing Machinery, p. 226-239 14 p. (SIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication).

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

    8 Scopus citations
  • 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
  • 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
  • Calibration, entropy rates, and memory in language models

    Braverman, M., Chen, X., Kakade, S., Narasimhan, K., Zhang, C. & Zhang, Y., 2020, 37th International Conference on Machine Learning, ICML 2020. Daume, H. & Singh, A. (eds.). International Machine Learning Society (IMLS), p. 1066-1076 11 p. (37th International Conference on Machine Learning, ICML 2020; vol. PartF168147-2).

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

    1 Scopus citations
  • 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
  • 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
  • Coding in undirected graphs is either very helpful or not helpful at all

    Braverman, M., Garg, S. & Schvartzman, A., Nov 1 2017, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. Papadimitriou, C. H. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 67).

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

    3 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
  • 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

  • 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
  • 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
  • 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
  • ETH hardness for densest-k-Subgraph with perfect completeness

    Braverman, M., Ko, Y. K., Rubinstein, A. & Weinstein, O., Jan 1 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1326-1341 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

    Open Access
    17 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
  • 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
  • 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
  • Hitting sets with near-Optimal error for read-Once branching programs

    Braverman, M., Cohen, G. & Garg, S., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 940-951 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    3 Scopus citations
  • 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
  • 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 complexity is computable

    Braverman, M. & Schneider, J., 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, 87. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 55).

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

    1 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
  • 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
  • Information value of two-prover games

    Braverman, M. & Ko, Y. K., Jan 1 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 94. 12

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

    1 Scopus citations
  • Interactive compression to external information

    Braverman, M. & Kol, G., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 760-772 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    1 Scopus citations
  • 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
  • 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
  • Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

    Braverman, M., Mao, J. & Weinberg, S. M., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 1444-1457 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 3).

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

    Open Access
    7 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
  • 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
  • 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
  • New separations results for external information

    Braverman, M. & Minzer, D., Jun 15 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 248-258 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
  • 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

  • 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
  • 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
  • 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
  • On simultaneous two-player combinatorial auctions

    Braverman, M., Mao, J. & Weinberg, S. M., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 2256-2273 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    10 Scopus citations
  • 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
  • On the computational power of radio channels

    Braverman, M., Kol, G., Oshman, R. & Tal, A., Oct 2019, 33rd International Symposium on Distributed Computing, DISC 2019. Suomela, J. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 146).

    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