All reports by Author Yael Tauman Kalai:

__
TR20-137
| 11th September 2020
__

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena#### Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

__
TR18-140
| 11th August 2018
__

Ilan Komargodski, Ran Raz, Yael Tauman Kalai#### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Revisions: 1

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

__
TR17-099
| 5th June 2017
__

Nir Bitansky, Omer Paneth, Yael Tauman Kalai#### Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 2

__
TR17-095
| 26th May 2017
__

Ran Gelles, Yael Tauman Kalai#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

__
TR16-077
| 12th May 2016
__

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai#### Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

__
TR15-092
| 31st May 2015
__

Yael Tauman Kalai, Ilan Komargodski#### Compressing Communication in Distributed Protocols

Revisions: 2

__
TR14-170
| 10th December 2014
__

Yael Tauman Kalai, Ran Raz#### On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

__
TR13-183
| 22nd December 2013
__

Yael Tauman Kalai, Ran Raz, Ron Rothblum#### How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

__
TR12-043
| 16th April 2012
__

Zvika Brakerski, Yael Tauman Kalai#### Efficient Interactive Coding Against Adversarial Noise

Revisions: 1

__
TR07-031
| 26th March 2007
__

Yael Tauman Kalai, Ran Raz#### Interactive PCP

__
TR03-015
| 20th March 2003
__

Yael Tauman Kalai#### On the (In)security of the Fiat-Shamir Paradigm

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>>

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>

Nir Bitansky, Omer Paneth, Yael Tauman Kalai

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

Ran Gelles, Yael Tauman Kalai

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

Yael Tauman Kalai, Ilan Komargodski

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

Yael Tauman Kalai, Ran Raz

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

Yael Tauman Kalai, Ran Raz, Ron Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>>

Zvika Brakerski, Yael Tauman Kalai

In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given ... more >>>

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership $x \in L$) is a

proof that can be verified by reading only one of its bits, with the

help of a very short interactive-proof.

We show that for membership in some languages $L$, there are

interactive-PCPs that are significantly shorter than the known

more >>>

Yael Tauman Kalai

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>