All reports by Author Hamidreza Jahanjou:

__
TR14-037
| 21st March 2014
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Succinct and explicit circuits for sorting and connectivity

__
TR13-099
| 6th July 2013
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Local reductions

Revisions: 3

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

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

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

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

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

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