All reports by Author Michal Koucky:

__
TR17-170
| 6th November 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Simulation Beats Richness: New Data-Structure Lower Bounds

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR16-165
| 30th October 2016
__

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Lower Bounds for Elimination via Weak Regularity

__
TR16-144
| 15th September 2016
__

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky#### Expander Construction in VNC${}^1$

Revisions: 2

__
TR15-138
| 25th August 2015
__

Michal Koucky#### Nonuniform catalytic space and the direct sum for space

Revisions: 1

__
TR14-053
| 15th April 2014
__

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman#### Computing with a full memory: Catalytic space

Revisions: 1

__
TR12-179
| 13th December 2012
__

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

__
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

__
TR10-113
| 16th July 2010
__

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak#### Pseudorandom Generators for Group Products

__
TR09-051
| 2nd July 2009
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy#### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

__
TR08-038
| 4th April 2008
__

Eric Allender, Michal Koucky#### Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR06-024
| 18th February 2006
__

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin#### Inverting onto functions might not be hard

__
TR05-136
| 14th November 2005
__

Anna Gal, Michal Koucky, Pierre McKenzie#### Incremental branching programs

__
TR04-044
| 1st June 2004
__

Eric Allender, Harry Buhrman, Michal Koucky#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

__
TR02-028
| 15th May 2002
__

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek#### Power from Random Strings

Revisions: 1

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

__
TR01-013
| 2nd February 2001
__

Michal Koucky#### Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{4.03})$

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [Annals of Mathematics, 2002], and show that this analysis can be formalized in the bounded-arithmetic system $VNC^1$ (corresponding to the ``$NC^1$ reasoning''). As a corollary, we prove the ... more >>>

Michal Koucky

This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has ... more >>>

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... 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 >>>

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Eric Allender, Michal Koucky

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

The class TFNP, defined by Megiddo and Papadimitriou, consists of

multivalued functions with values that are polynomially verifiable

and guaranteed to exist. Do we have evidence that such functions are

hard, for example, if TFNP is computable in polynomial-time does

this imply the polynomial-time hierarchy collapses?

We give a relativized ... more >>>

Anna Gal, Michal Koucky, Pierre McKenzie

In this paper we propose the study of a new model of restricted

branching programs which we call incremental branching programs.

This is in line with the program proposed by Cook in 1974 as an

approach for separating the class of problems solvable in logarithmic

space from problems solvable ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky

We investigate the question of whether one can characterize complexity

classes (such as PSPACE or NEXP) in terms of efficient

reducibility to the set of Kolmogorov-random strings R_C.

We show that this question cannot be posed without explicitly dealing

with issues raised by the choice of universal

machine in the ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

We consider sets of strings with high Kolmogorov complexity, mainly

in resource-bounded settings but also in the traditional

recursion-theoretic sense. We present efficient reductions, showing

that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Michal Koucky

The paper presents a simple construction of polynomial length universal

traversal sequences for cycles. These universal traversal sequences are

log-space (even $NC^1$) constructible and are of length $O(n^{4.03})$. Our

result improves the previously known upper-bound $O(n^{4.76})$ for

log-space constructible universal traversal sequences for cycles.