Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSUDORANDOMNESS:
Reports tagged with psudorandomness:
TR20-057 | 20th April 2020
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

TR22-025 | 15th February 2022
Oliver Korten

Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the compression problem,'' where we are given ... more >>>

ISSN 1433-8092 | Imprint