Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Periklis Papakonstantinou:

TR16-085 | 28th May 2016
Shiteng Chen, Periklis Papakonstantinou

Depth-reduction for composites

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... more >>>

TR15-122 | 29th July 2015
Shiteng Chen, Periklis Papakonstantinou

Correlation lower bounds from correlation upper bounds

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

TR14-124 | 7th October 2014
Periklis Papakonstantinou

The Depth Irreducibility Hypothesis

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

TR13-189 | 21st December 2013
Periklis Papakonstantinou, Dominik Scheder, Hao Song

Overlays and Limited Memory Communication Mode(l)s

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

TR12-167 | 16th November 2012
Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

How powerful are the DDH hard groups?

The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure ... more >>>

TR12-027 | 29th March 2012
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

TR12-005 | 13th January 2012
Periklis Papakonstantinou, Guang Yang

A remark on one-wayness versus pseudorandomness

Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the
pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose
$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$ is a pseudorandom generator with stretch $\ell(n)> n$. Let $M_R\in\{0,1\}^{m(n)\times \ell(n)}$ be a linear ... more >>>

TR11-117 | 3rd September 2011
Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

Pseudorandomness for read-once formulas

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

TR09-039 | 6th April 2009
Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

Polynomial Time with Restricted Use of Randomness

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

ISSN 1433-8092 | Imprint