Gillat Kol

Zhijun Zhang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

The Rate of Interactive Codes Is Bounded Away from 1.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Protecting Single-Hop Radio Networks from Message Drops.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Circuits resilient to short-circuit errors.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Distributed Zero-Knowledge Proofs Over Networks.

[BibT_eX]

[DOI]

Aviv Bick

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Rounds vs Communication Tradeoffs for Maximal Independent Sets.

[BibT_eX]

[DOI]

Sepehr Assadi

Zhijun Zhang

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Optimal error resilience of adaptive message exchange.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Computation over the Noisy Broadcast Channel with Malicious Parties.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Statistically Near-Optimal Hypothesis Selection.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Near Optimal Distributed Learning of Halfspaces with Two Parties.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Interactive error resilience beyond 2/7.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Noisy Beeps.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets.

[BibT_eX]

[DOI]

Sepehr Assadi

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility.

[BibT_eX]

[DOI]

CoRR, 2019

On the Computational Power of Radio Channels.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Radio Network Coding Requires Logarithmic Overhead.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Explicit Capacity Approaching Coding for Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

Interactive coding over the noisy broadcast channel.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Interactive compression to external information.

[BibT_eX]

[DOI]

Mark Braverman

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Interactive Distributed Proofs.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

A Candidate for a Strong Separation of Information and Communication.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Interactive Compression for Multi-Party Protocol.

[BibT_eX]

[DOI]

Dafna Sadeh

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Time-space hardness of learning sparse parities.

[BibT_eX]

[DOI]

Avishay Tal

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Interactive compression for product distributions.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Exponential separation of communication and external information.

[BibT_eX]

[DOI]

Anat Ganor

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Towards Optimal Deterministic Coding for Interactive Communication.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Exponential Separation of Information and Communication for Boolean Functions.

[BibT_eX]

[DOI]

Anat Ganor

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Direct sum fails for zero error average communication.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Exponential Separation of Information and Communication.

[BibT_eX]

[DOI]

Anat Ganor

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Interactive channel capacity.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Competing provers protocols for circuit evaluation.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Covering CSPs.

[BibT_eX]

[DOI]

Irit Dinur

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Bounds on locally testable codes with unique tests.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2009

Bounds on 2-Query Locally Testable Codes with Affine Tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

Cryptography and Game Theory: Designing Protocols for Exchanging Information.

[BibT_eX]

[DOI]

Moni Naor

Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Games for exchanging information.

[BibT_eX]

[DOI]