Gillat Kol
Contact Expert

View Scopus Profile

Gillat Kol

Former affiliation
Calculated based on number of publications stored in Pure and citations from Scopus
20082024

Research activity per year

  • 44 Conference contribution
  • 7 Article
  • 1 Conference article

Search results

  • 2024

    Information Dissemination via Broadcasts in the Presence of Adversarial Noise

    Efremenko, K., Kol, G., Paramonov, D., Raz, R. & Saxena, R. R., Jul 2024, 39th Computational Complexity Conference, CCC 2024. Santhanam, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 19. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 300).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Optimal Multi-pass Lower Bounds for MST in Dynamic Streams

    Assadi, S., Kol, G. & Zhang, Z., Jun 10 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). Association for Computing Machinery, p. 835-846 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
  • 2023

    Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

    Kol, G., Paramonov, D., Saxena, R. R. & Yu, H., Jan 1 2023, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Kalai, Y. T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 80. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 251).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations

  • Interactive Coding with Small Memory

    Efremenko, K., Haeupler, B., Kalai, Y. T., Kol, G., Resch, N. & Saxena, R. R., 2023, 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. Association for Computing Machinery, p. 3587-3613 27 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2023-January).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., Jan 1 2023, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Kalai, Y. T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 251).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Protecting Single-Hop Radio Networks from Message Drops

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., Jul 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Etessami, K., Feige, U. & Puppis, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 53. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 261).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations

  • The Rate of Interactive Codes Is Bounded Away from 1

    Efremenko, K., Kol, G., Paramonov, D. & Saxena, R. R., Jun 2 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 1424-1437 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access

  • Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

    Chen, L., Kol, G., Paramonov, D., Saxena, R. R., Song, Z. & Yu, H., 2023, 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. Association for Computing Machinery, p. 878-924 47 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2023-January).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Scopus citations
  • 2022

    Binary Codes with Resilience Beyond 1/4 via Interaction

    Efremenko, K., Kol, G., Saxena, R. R. & Zhang, Z., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 1-12 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    2 Scopus citations

  • Circuits resilient to short-circuit errors

    Efremenko, K., Haeupler, B., Kalai, Y. T., Kamath, P., Kol, G., Resch, N. & Saxena, R. R., Sep 6 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 582-594 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • 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 proceeding › Conference contribution

    13 Scopus citations

  • Rounds vs Communication Tradeoffs for Maximal Independent Sets

    Assadi, S., Kol, G. & Zhang, Z., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 1193-1204 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    7 Scopus citations

  • 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 proceeding › Conference contribution

    Open Access
    1 Scopus citations

  • 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 proceeding › Conference contribution

    5 Scopus citations
  • 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 proceeding › Conference contribution

    Open Access
    19 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 proceeding › Conference contribution

    7 Scopus citations

  • Exponential separation of communication and external information

    GANOR, A., KOL, G. & RAZ, R., 2021, In: SIAM Journal on Computing. 50, 3, p. 236-254 19 p.

    Research output: Contribution to journal › Article › peer-review

    2 Scopus citations

  • Near Optimal Distributed Learning of Halfspaces with Two Parties

    Braverman, M., Kol, G., Moran, S. & Saxena, R. R., 2021, In: Proceedings of Machine Learning Research. 134, p. 724-758 35 p.

    Research output: Contribution to journal › Conference article › peer-review

    3 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 proceeding › Conference contribution

    7 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 proceeding › Conference contribution

    3 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 proceeding › Conference contribution

    4 Scopus citations

  • 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 proceeding › Conference contribution

    5 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 proceeding › Conference contribution

    7 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 proceeding › Conference contribution

    Open Access
    25 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 proceeding › Conference contribution

    11 Scopus citations
  • 2019

    Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., Mar 11 2019, In: Computational Complexity. 28, 1, p. 1-25 25 p.

    Research output: Contribution to journal › Article › peer-review

    4 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 proceeding › Conference contribution

    1 Scopus citations

  • 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 proceeding › Conference contribution

    8 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 proceeding › Conference contribution

    3 Scopus citations

  • Explicit Capacity Approaching Coding for Interactive Communication

    Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N. & Wigderson, A., Oct 2018, In: IEEE Transactions on Information Theory. 64, 10, p. 6546-6560 15 p., 8345651.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    14 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 proceeding › Conference contribution

    9 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 proceeding › Conference contribution

    5 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 proceeding › Conference contribution

    38 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 proceeding › Conference contribution

    4 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 proceeding › Conference contribution

    Open Access
    34 Scopus citations
  • 2016

    Bounds on 2-query Locally Testable Codes with affine tests

    Kol, G. & Raz, R., Aug 1 2016, In: Information Processing Letters. 116, 8, p. 521-525 5 p.

    Research output: Contribution to journal › Article › peer-review

    Open Access

  • Direct Sum Fails for Zero-Error Average Communication

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., Nov 1 2016, In: Algorithmica. 76, 3, p. 782-795 14 p.

    Research output: Contribution to journal › Article › peer-review

    1 Scopus citations

  • 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 proceeding › Conference contribution

    Open Access
    16 Scopus citations

  • Exponential separation of information and communication for boolean functions

    Ganor, A., Kol, G. & Raz, R., Nov 2016, In: Journal of the ACM. 63, 5, 46.

    Research output: Contribution to journal › Article › peer-review

    19 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 proceeding › Conference contribution

    Open Access
    17 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 proceeding › Conference contribution

    27 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 proceeding › Conference contribution

    21 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 proceeding › Conference contribution

    14 Scopus citations

  • Competing-provers protocols for circuit evaluation

    Kol, G. & Raz, R., Aug 9 2014, In: Theory of Computing. 10, p. 107-131 25 p.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    1 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 proceeding › Conference 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 proceeding › Conference contribution

    Open Access
    37 Scopus citations
  • 2013

    Competing provers protocols for circuit evaluation

    Kol, G. & Raz, R., 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 proceeding › Conference contribution

    Open Access
    4 Scopus citations

  • Covering CSPs

    Dinur, I. & Kol, G., 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 proceeding › Conference contribution

    8 Scopus citations

  • Interactive channel capacity

    Kol, G. & Raz, R., 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 proceeding › Conference contribution

    Open Access
    74 Scopus citations
  • 2012

    Bounds on locally testable codes with unique tests

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

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations