All reports by Author Kristoffer Arnsfelt Hansen:

__
TR13-021
| 5th February 2013
__

Kristoffer Arnsfelt Hansen, Vladimir Podolskii#### Polynomial threshold functions and Boolean threshold circuits

__
TR12-025
| 23rd March 2012
__

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin#### Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques

__
TR11-150
| 4th November 2011
__

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola#### Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

__
TR06-079
| 12th June 2006
__

Kristoffer Arnsfelt Hansen#### Lower Bounds for Circuits with Few Modular Gates using Exponential Sums

__
TR03-025
| 14th April 2003
__

Kristoffer Arnsfelt Hansen#### Constant width planar computation characterizes ACC0

__
TR02-066
| 24th October 2002
__

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay#### Circuits on Cylinders

Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than $\xi/2$, where $\xi = \frac{3-\sqrt5}{2} \approx 0.382$, is not possible by a polynomial time algorithm. ... more >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code

$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,

using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

Kristoffer Arnsfelt Hansen

We prove that any AC0 circuit augmented with {epsilon log^2 n}

MOD_m gates and with a MAJORITY gate at the output, require size

n^{Omega(log n)} to compute MOD_l, when l has a prime

factor not dividing m and epsilon is sufficiently small. We

also obtain ...
more >>>

Kristoffer Arnsfelt Hansen

We obtain a characterization of ACC0 in terms of a natural class of

constant width circuits, namely in terms of constant width polynomial

size planar circuits. This is shown via a characterization of the

class of acyclic digraphs which can be embedded on a cylinder surface

in such a way ...
more >>>

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

We consider the computational power of constant width polynomial

size cylindrical circuits and nondeterministic branching programs.

We show that every function computed by a Pi2 o MOD o AC0 circuit

can also be computed by a constant width polynomial size cylindrical

nondeterministic branching program (or cylindrical circuit) and

that ...
more >>>