All reports by Author Periklis Papakonstantinou:

__
TR22-159
| 18th November 2022
__

Songhua He, Periklis Papakonstantinou#### Deep Neural Networks: The Missing Complexity Parameter

__
TR16-085
| 28th May 2016
__

Shiteng Chen, Periklis Papakonstantinou#### Depth-reduction for composites

__
TR15-122
| 29th July 2015
__

Shiteng Chen, Periklis Papakonstantinou#### Correlation lower bounds from correlation upper bounds

__
TR14-124
| 7th October 2014
__

Periklis Papakonstantinou#### The Depth Irreducibility Hypothesis

__
TR13-189
| 21st December 2013
__

Periklis Papakonstantinou, Dominik Scheder, Hao Song#### Overlays and Limited Memory Communication Mode(l)s

__
TR12-167
| 16th November 2012
__

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis#### How powerful are the DDH hard groups?

__
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

__
TR12-005
| 13th January 2012
__

Periklis Papakonstantinou, Guang Yang#### A remark on one-wayness versus pseudorandomness

__
TR11-117
| 3rd September 2011
__

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan#### Pseudorandomness for read-once formulas

__
TR09-039
| 6th April 2009
__

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos#### Polynomial Time with Restricted Use of Randomness

Songhua He, Periklis Papakonstantinou

Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>>

Shiteng Chen, Periklis Papakonstantinou

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

Shiteng Chen, Periklis Papakonstantinou

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

Periklis Papakonstantinou

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

Periklis Papakonstantinou, Dominik Scheder, Hao Song

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

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

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

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

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

Periklis Papakonstantinou, Guang Yang

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

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

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

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

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