All reports by Author Ronen Shaltiel:

__
TR21-153
| 9th November 2021
__

Ronen Shaltiel, Emanuele Viola#### On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

__
TR20-133
| 8th September 2020
__

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma#### Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

__
TR20-094
| 24th June 2020
__

Ronen Shaltiel#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

__
TR20-047
| 16th April 2020
__

Ronen Shaltiel, Jad Silbak#### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity

Revisions: 2

__
TR19-090
| 27th June 2019
__

Ronen Shaltiel, Swastik Kopparty, Jad Silbak#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2

__
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

Revisions: 1

__
TR18-071
| 15th April 2018
__

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak#### Computational Two-Party Correlation

Revisions: 1

__
TR18-061
| 6th April 2018
__

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola#### Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 5

__
TR16-134
| 29th August 2016
__

Ronen Shaltiel, Jad Silbak#### Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

Revisions: 1

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
TR15-051
| 5th April 2015
__

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR11-127
| 18th September 2011
__

Ronen Shaltiel#### Dispersers for affine sources with sub-polynomial entropy

__
TR11-016
| 7th February 2011
__

Sergei Artemenko, Ronen Shaltiel#### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

__
TR10-186
| 2nd December 2010
__

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola#### On beating the hybrid argument

__
TR10-129
| 16th August 2010
__

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel#### Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

__
TR10-037
| 8th March 2010
__

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

__
TR07-130
| 3rd December 2007
__

Ronen Shaltiel, Emanuele Viola#### Hardness amplification proofs require majority

__
TR07-069
| 29th July 2007
__

Ronen Shaltiel, Chris Umans#### Low-end uniform hardness vs. randomness tradeoffs for AM

__
TR05-145
| 5th December 2005
__

Ronen Shaltiel#### How to get more mileage from randomness extractors

__
TR05-109
| 28th September 2005
__

Ariel Gabizon, Ran Raz, Ronen Shaltiel#### Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

__
TR04-115
| 1st December 2004
__

Iftach Haitner, Ronen Shaltiel#### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

__
TR04-086
| 12th October 2004
__

Ronen Shaltiel, Chris Umans#### Pseudorandomness for Approximate Counting and Sampling

__
TR01-009
| 5th January 2001
__

Ronen Shaltiel#### Towards proving strong direct product theorems

__
TR00-059
| 11th August 2000
__

Omer Reingold, Ronen Shaltiel, Avi Wigderson#### Extracting Randomness via Repeated Condensing

__
TR00-009
| 21st February 2000
__

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson#### Extractors and pseudo-random generators with optimal seed length

Ronen Shaltiel, Emanuele Viola

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1\}^r \to \{0,1\}^m$ that fool circuits of size $m$, assuming the existence of explicit hard functions. A ``high-end PRG'' with seed length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.

A $q$-query local list-decoder is ...
more >>>

Ronen Shaltiel

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

Ronen Shaltiel, Jad Silbak

We consider codes for space bounded channels. This is a model for communication under noise that was introduced 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 >>>

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

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 >>>

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

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 >>>

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

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:

\begin{itemize}

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

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

We study how well can $q$-query decision trees distinguish between the

following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.

variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge

2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of

size ...
more >>>

Ronen Shaltiel, Jad Silbak

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 >>>

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

Ronen Shaltiel

We construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $D:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $D(V)=\set{0,1}$. This improves the best previous construction of Ben-Sasson and Kopparty ... more >>>

Sergei Artemenko, Ronen Shaltiel

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

The {\em hybrid argument}

allows one to relate

the {\em distinguishability} of a distribution (from

uniform) to the {\em

predictability} of individual bits given a prefix. The

argument incurs a loss of a factor $k$ equal to the

bit-length of the

distributions: $\epsilon$-distinguishability implies only

$\epsilon/k$-predictability. ...
more >>>

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

Ronen Shaltiel, Chris Umans

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

Ronen Shaltiel

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>

Ariel Gabizon, Ran Raz, Ronen Shaltiel

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that

there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly

distributed and independent of each other, and the remaining $n-k$ variables

are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n

\ar \B^m$ which on ...
more >>>

Iftach Haitner, Ronen Shaltiel

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another

polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any

additional information but the validity of the claim.

Naor ... more >>>

Ronen Shaltiel, Chris Umans

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

Ronen Shaltiel

A fundamental question of complexity theory is the direct product

question. Namely weather the assumption that a function $f$ is hard on

average for some computational class (meaning that every algorithm from

the class has small advantage over random guessing when computing $f$)

entails that computing $f$ on ...
more >>>

Omer Reingold, Ronen Shaltiel, Avi Wigderson

On an input probability distribution with some (min-)entropy

an {\em extractor} outputs a distribution with a (near) maximum

entropy rate (namely the uniform distribution).

A natural weakening of this concept is a condenser, whose

output distribution has a higher entropy rate than the

input distribution (without losing

much of ...
more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>