Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jad Silbak:

TR19-090 | 27th June 2019
Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Quasilinear time list-decodable codes for space bounded channels

Revisions: 1

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>

TR19-081 | 31st May 2019
Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

TR18-071 | 15th April 2018
Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

Computational Two-Party Correlation

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\item We develop new tools to ... more >>>

TR16-134 | 29th August 2016
Ronen Shaltiel, Jad Silbak

Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

ISSN 1433-8092 | Imprint