Gillat Kol

Zhijun Zhang

Electron. Colloquium Comput. Complex., 2023

2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Circuits Resilient to Short-Circuit Errors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Round-vs-Resilience Tradeoffs for Binary Feedback Channels.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Rounds vs Communication Tradeoffs for Maximal Independent Sets.

[BibT_eX]

[DOI]

Sepehr Assadi

Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Distributed Zero-Knowledge Proofs Over Networks.

[BibT_eX]

[DOI]

Aviv Bick

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

2021

Exponential Separation of Communication and External Information.

[BibT_eX]

[DOI]

Anat Ganor

SIAM J. Comput., 2021

Optimal Error Resilience of Adaptive Message Exchange.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Computation Over the Noisy Broadcast Channel with Malicious Parties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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]

Electron. Colloquium Comput. Complex., 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

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

Radio Network Coding Requires Logarithmic Overhead.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Noisy Beeps.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Comput. Complex., 2019

On the Computational Power of Radio Channels.

[BibT_eX]

[DOI]

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

2018

Explicit Capacity Approaching Coding for Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 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]

Raghuvansh R. Saxena

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 Coding Over the Noisy Broadcast Channel.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Interactive Compression for Multi-Party Protocol.

[BibT_eX]

[DOI]

Dafna Sadeh

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

2016

Bounds on 2-query Locally Testable Codes with affine tests.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2016

Time-Space Hardness of Learning Sparse Parities.

[BibT_eX]

[DOI]

Avishay Tal

Electron. Colloquium Comput. Complex., 2016

2015

Interactive Compression for Product Distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Towards Optimal Deterministic Coding for Interactive Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

Exponential Separation of Information and Communication for Boolean Functions.

[BibT_eX]

[DOI]

Anat Ganor

Electron. Colloquium Comput. Complex., 2014

Exponential Separation of Information and Communication.

[BibT_eX]

[DOI]

Anat Ganor

Electron. Colloquium Comput. Complex., 2014

2013

Interactive Channel Capacity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Direct Sum Fails for Zero Error Average Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Covering CSPs.

[BibT_eX]

[DOI]

Irit Dinur

Electron. Colloquium Comput. Complex., 2012

Bounds on locally testable codes with unique tests.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Competing Provers Protocols for Circuit Evaluation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

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]