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

Research activity per year

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

Search results

  • 2022

    Distributed Zero-Knowledge Proofs Over Networks

    Bick, A., Kol, G. & Oshman, R., 2022, ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, p. 2426-2458 33 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2022-January).

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

  • Statistically Near-Optimal Hypothesis Selection

    Bousquet, O., Braverman, M., Kol, G., Efremenko, K. & Moran, S., 2022, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE Computer Society, p. 909-919 11 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-February).

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

  • Tight Bounds for General Computation in Noisy Broadcast Networks

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., 2022, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE Computer Society, p. 634-645 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-February).

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

  • 2021

    Almost optimal super-constant-pass streaming lower bounds for reachability

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., 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. 570-583 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    2 Scopus citations
  • Computation over the noisy broadcast channel with malicious parties

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., Feb 1 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 82. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

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

    2 Scopus citations
  • Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., Jul 1 2021, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Bansal, N., Merelli, E. & Worrell, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 198).

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

    2 Scopus citations
  • Optimal error resilience of adaptive message exchange

    Efremenko, K., Kol, G. & Saxena, R. R., 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. 1235-1247 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    1 Scopus citations
  • 2020

    Binary interactive error resilience beyond

    Efremenko, K., Kol, G. & Saxena, R. R., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 470-481 12 p. 9317957. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

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

  • Interactive error resilience beyond 2/7

    Efremenko, K., Kol, G. & Saxena, R. R., Jun 8 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 565-578 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    3 Scopus citations
  • Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

    Assadi, S., Kol, G. & Oshman, R., Jul 31 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 79-88 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

    2 Scopus citations
  • Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems

    Assadi, S., Kol, G., Saxena, R. R. & Yu, H., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 354-364 11 p. 9317902. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

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

    4 Scopus citations
  • Noisy Beeps

    Efremenko, K., Kol, G. & Saxena, R. R., Jul 31 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 418-427 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

    5 Scopus citations
  • 2019

    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

  • Radio network coding requires logarithmic overhead

    Efremenko, K., Kol, G. & Saxena, R., Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 348-369 22 p. 8948679. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

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

    3 Scopus citations
  • 2018

    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
  • Interactive coding over the noisy broadcast channel

    Efremenko, K., Kol, G. & Saxena, R., 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. 890-901 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    5 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

    3 Scopus citations
  • Interactive distributed proofs

    Kol, G., Oshman, R. & Saxena, R. R., Jul 23 2018, PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 255-264 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

    19 Scopus citations
  • 2017

    Interactive compression for multi-party protocols

    Kol, G., Oshman, R. & Sadeh, D., Oct 1 2017, 31st International Symposium on Distributed Computing, DISC 2017. Richa, A. W. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 91).

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

    3 Scopus citations
  • Time-space hardness of learning sparse parities

    Kol, G., Raz, R. & Tal, A., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 1067-1080 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

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

    16 Scopus citations
  • 2016

    Exponential separation of communication and external information

    Ganor, A., Kol, G. & Raz, R., 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. 977-986 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

    15 Scopus citations
  • Interactive compression for product distributions

    Kol, G., 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. 987-998 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

    13 Scopus citations
  • Towards optimal deterministic coding for interactive communication

    Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N. & Wigderson, A., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 1922-1936 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 3).

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

    Open Access
    20 Scopus citations
  • 2015

    Exponential separation of information and communication for boolean functions

    Ganor, A., Kol, G. & Raz, R., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 557-566 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

    20 Scopus citations
  • 2014

    Approximate nonnegative rank is equivalent to the smooth rectangle bound

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 701-712 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

    12 Scopus citations
  • Direct sum fails for zero error average communication

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., 2014, ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 517-522 6 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

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

    2 Scopus citations
  • Exponential separation of information and communication

    Ganor, A., Kol, G. & Raz, R., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 176-185 10 p. 6979002. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    36 Scopus citations
  • 2013

    Competing provers protocols for circuit evaluation

    Kol, G. & Raz, R., Feb 11 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 473-484 12 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

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

    4 Scopus citations
  • Covering CSPs

    Dinur, I. & Kol, G., Oct 21 2013, Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013. p. 207-218 12 p. 6597763. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

    8 Scopus citations
  • Interactive channel capacity

    Kol, G. & Raz, R., Jul 11 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 715-724 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    67 Scopus citations
  • 2012

    Bounds on locally testable codes with unique tests

    Kol, G. & Raz, R., Feb 6 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 190-202 13 p.

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

    1 Scopus citations
  • 2008

    Cryptography and game theory: Designing protocols for exchanging information

    Kol, G. & Naor, M., 2008, Theory of Cryptography - Fifth Theory of Cryptography Conference, TCC 2008, Proceedings. p. 320-339 20 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4948 LNCS).

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

    137 Scopus citations
  • Games for exchanging information

    Kol, G. & Naor, M., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 423-432 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    96 Scopus citations