Gillat Kol - RankMe

100 papers A* 33A 14B 1Journal 51Unranked 1

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