Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROBABILISTIC METHOD:
Reports tagged with Probabilistic Method:
TR97-012 | 19th March 1997
Luca Trevisan

#### On Local versus Global Satisfiability

We prove an extremal combinatorial result regarding
the fraction of satisfiable clauses in boolean CNF
formulae enjoying a locally checkable property, thus
solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint
satisfaction ... more >>>

TR97-039 | 11th September 1997
Pierluigi Crescenzi, Luca Trevisan

We introduce a simple technique to obtain reductions
between optimization constraint satisfaction problems. The
technique uses the probabilistic method to reduce the size of
disjunctions. As a first application, we prove the
MAX NP-completeness of MAX 3SAT without using the PCP theorem
(thus solving an open ... more >>>

TR98-047 | 21st August 1998

#### Extracting All the Randomness from a Weakly Random Source

In this paper, we give explicit constructions of extractors which work for
a source of any min-entropy on strings of length $n$. The first
construction extracts any constant fraction of the min-entropy using
O(log^2 n) additional random bits. The second extracts all the
min-entropy using O(log^3 n) additional random ... more >>>

TR99-046 | 17th November 1999
Ran Raz, Omer Reingold, Salil Vadhan

#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

We give explicit constructions of extractors which work for a source of
any min-entropy on strings of length n. These extractors can extract any
constant fraction of the min-entropy using O(log^2 n) additional random
bits, and can extract all the min-entropy using O(log^3 n) additional
random bits. Both of these ... more >>>

TR11-131 | 29th September 2011
Rahul Santhanam, Srikanth Srinivasan

#### On the Limits of Sparsification

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

TR11-144 | 2nd November 2011
Greg Kuperberg, Shachar Lovett, Ron Peled

#### Probabilistic existence of rigid combinatorial structures

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

TR12-017 | 1st March 2012
Venkatesan Guruswami, Srivatsan Narayanan

#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

TR13-118 | 2nd September 2013
Mahdi Cheraghchi, Venkatesan Guruswami

#### Capacity of Non-Malleable Codes

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

TR13-126 | 11th September 2013
Arman Fazeli, Shachar Lovett, Alex Vardy

#### Nontrivial t-designs over finite fields exist for all t

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

ISSN 1433-8092 | Imprint