Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Eric Miles:

TR14-037 | 21st March 2014
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Succinct and explicit circuits for sorting and connectivity

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

TR13-099 | 6th July 2013
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Local reductions

Revisions: 3

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on ... more >>>

TR13-003 | 2nd January 2013
Eric Miles, Emanuele Viola

Shielding circuits with groups

Revisions: 2

We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression ... more >>>

TR12-125 | 2nd October 2012
Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

From RAM to SAT

Revisions: 1

Common presentations of the NP-completeness of SAT suffer
from two drawbacks which hinder the scope of this
flagship result. First, they do not apply to machines
equipped with random-access memory, also known as
direct-access memory, even though this feature is
critical in basic algorithms. Second, they incur a
quadratic blow-up ... more >>>

TR12-019 | 2nd March 2012
Eric Miles, Emanuele Viola

On the complexity of constructing pseudorandom functions (especially when they don't exist)

We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only $k(n)$ oracle ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

ISSN 1433-8092 | Imprint