Gillat Kol

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 70

Top Topics

Root Mean Square

Error Resilience

Boolean Functions

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. STOC (2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. CCC (2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
The Rate of Interactive Codes is Bounded Away from 1. Electron. Colloquium Comput. Complex. (2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Protecting Single-Hop Radio Networks from Message Drops. Electron. Colloquium Comput. Complex. (2023)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Protecting Single-Hop Radio Networks from Message Drops. ICALP (2023)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. ITCS (2023)
Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
Interactive Coding with Small Memory. SODA (2023)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams. Electron. Colloquium Comput. Complex. (2023)
Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. ITCS (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. SODA (2023)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams. CoRR (2023)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
The Rate of Interactive Codes Is Bounded Away from 1. STOC (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. Electron. Colloquium Comput. Complex. (2022)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds. Electron. Colloquium Comput. Complex. (2022)
Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. Electron. Colloquium Comput. Complex. (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. CoRR (2022)
Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
Statistically Near-Optimal Hypothesis Selection. FOCS (2022)
Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
Circuits Resilient to Short-Circuit Errors. Electron. Colloquium Comput. Complex. (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. Electron. Colloquium Comput. Complex. (2022)
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
Binary Codes with Resilience Beyond 1/4 via Interaction. FOCS (2022)
Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai
Interactive Coding with Small Memory. Electron. Colloquium Comput. Complex. (2022)
Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. (2022)
Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
Circuits resilient to short-circuit errors. STOC (2022)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS (2022)
Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. FOCS (2022)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
Binary Codes with Resilience Beyond 1/4 via Interaction. Electron. Colloquium Comput. Complex. (2022)
Aviv Bick, Gillat Kol, Rotem Oshman
Distributed Zero-Knowledge Proofs Over Networks. SODA (2022)
Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
Near Optimal Distributed Learning of Halfspaces with Two Parties. COLT (2021)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Optimal Error Resilience of Adaptive Message Exchange. Electron. Colloquium Comput. Complex. 28 (2021)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Communication and External Information. SIAM J. Comput. 50 (3) (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. ICALP (2021)
Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran
Statistically Near-Optimal Hypothesis Selection. CoRR (2021)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. Electron. Colloquium Comput. Complex. 28 (2021)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Computation over the Noisy Broadcast Channel with Malicious Parties. ITCS (2021)
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
Optimal error resilience of adaptive message exchange. STOC (2021)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Tight Bounds for General Computation in Noisy Broadcast Networks. Electron. Colloquium Comput. Complex. 28 (2021)
Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
Statistically Near-Optimal Hypothesis Selection. FOCS (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR (2021)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Computation Over the Noisy Broadcast Channel with Malicious Parties. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Almost optimal super-constant-pass streaming lower bounds for reachability. STOC (2021)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$). Electron. Colloquium Comput. Complex. 28 (2021)
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. FOCS (2020)
Sepehr Assadi, Gillat Kol, Rotem Oshman
Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets. PODC (2020)
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
Interactive error resilience beyond 2/7. STOC (2020)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Interactive Error Resilience Beyond $\frac{2}{7}$. Electron. Colloquium Comput. Complex. 27 (2020)
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
Noisy Beeps. PODC (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. CoRR (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. FOCS (2020)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Comput. Complex. 28 (1) (2019)
Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. CoRR (2019)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Radio Network Coding Requires Logarithmic Overhead. Electron. Colloquium Comput. Complex. 26 (2019)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Noisy Beeps. Electron. Colloquium Comput. Complex. 26 (2019)
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
On the Computational Power of Radio Channels. DISC (2019)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Radio Network Coding Requires Logarithmic Overhead. FOCS (2019)
Mark Braverman, Gillat Kol
Interactive compression to external information. STOC (2018)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Interactive coding over the noisy broadcast channel. STOC (2018)
Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
A Candidate for a Strong Separation of Information and Communication. ITCS (2018)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Explicit Capacity Approaching Coding for Interactive Communication. IEEE Trans. Inf. Theory 64 (10) (2018)
Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena
Interactive Distributed Proofs. PODC (2018)
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Interactive Coding Over the Noisy Broadcast Channel. Electron. Colloquium Comput. Complex. 24 (2017)
Gillat Kol, Rotem Oshman, Dafna Sadeh
Interactive Compression for Multi-Party Protocol. DISC (2017)
Gillat Kol, Ran Raz, Avishay Tal
Time-space hardness of learning sparse parities. STOC (2017)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication for Boolean Functions. J. ACM 63 (5) (2016)
Gillat Kol, Ran Raz, Avishay Tal
Time-Space Hardness of Learning Sparse Parities. Electron. Colloquium Comput. Complex. 23 (2016)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct Sum Fails for Zero-Error Average Communication. Algorithmica 76 (3) (2016)
Gillat Kol, Ran Raz
Bounds on 2-query Locally Testable Codes with affine tests. Inf. Process. Lett. 116 (8) (2016)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Towards Optimal Deterministic Coding for Interactive Communication. SODA (2016)
Gillat Kol
Interactive compression for product distributions. STOC (2016)
Anat Ganor, Gillat Kol, Ran Raz
Exponential separation of communication and external information. STOC (2016)
Gillat Kol
Interactive Compression for Product Distributions. Electron. Colloquium Comput. Complex. 22 (2015)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Communication and External Information. Electron. Colloquium Comput. Complex. 22 (2015)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication for Boolean Functions. STOC (2015)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Towards Optimal Deterministic Coding for Interactive Communication. Electron. Colloquium Comput. Complex. 22 (2015)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication for Boolean Functions. Electron. Colloquium Comput. Complex. 21 (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound. ICALP (1) (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Electron. Colloquium Comput. Complex. 21 (2014)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Gillat Kol, Ran Raz
Competing-Provers Protocols for Circuit Evaluation. Theory Comput. 10 (2014)
Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication. FOCS (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct sum fails for zero error average communication. ITCS (2014)
Gillat Kol, Ran Raz
Competing provers protocols for circuit evaluation. ITCS (2013)
Gillat Kol, Ran Raz
Interactive Channel Capacity. Electron. Colloquium Comput. Complex. 20 (2013)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct Sum Fails for Zero Error Average Communication. Electron. Colloquium Comput. Complex. 20 (2013)
Gillat Kol, Ran Raz
Interactive channel capacity. STOC (2013)
Irit Dinur, Gillat Kol
Covering CSPs. Computational Complexity Conference (2013)
Irit Dinur, Gillat Kol
Covering CSPs. Electron. Colloquium Comput. Complex. 19 (2012)
Gillat Kol, Ran Raz
Bounds on locally testable codes with unique tests. ITCS (2012)
Gillat Kol, Ran Raz
Competing Provers Protocols for Circuit Evaluation. Electron. Colloquium Comput. Complex. 18 (2011)
Gillat Kol, Ran Raz
Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist. Electron. Colloquium Comput. Complex. 16 (2009)
Gillat Kol, Ran Raz
Bounds on 2-Query Locally Testable Codes with Affine Tests. Electron. Colloquium Comput. Complex. 16 (2009)
Gillat Kol, Moni Naor
Games for exchanging information. STOC (2008)
Gillat Kol, Moni Naor
Cryptography and Game Theory: Designing Protocols for Exchanging Information. TCC (2008)