A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**K**

__
TR17-088
| 10th May 2017
__

Elena Grigorescu, Akash Kumar, Karl Wimmer#### K-Monotonicity is Not Testable on the Hypercube

Revisions: 1

__
TR08-058
| 1st June 2008
__

Zeev Dvir, Avi Wigderson#### Kakeya sets, new mergers and old extractors

__
TR08-066
| 16th July 2008
__

Noga Alon, Shai Gutner#### Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

__
TR04-102
| 20th October 2004
__

Thomas Holenstein#### Key Agreement from Weak Bit Agreement

__
TR21-049
| 1st April 2021
__

Juraj Hromkovic#### Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

Revisions: 1

__
TR08-109
| 10th November 2008
__

Marc Kaplan, Sophie Laplante#### Kolmogorov complexity and combinatorial methods in communication complexity

__
TR01-086
| 29th October 2001
__

Nikolay Vereshchagin#### Kolmogorov Complexity Conditional to Large Integers

__
TR09-071
| 1st September 2009
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Kolmogorov Complexity in Randomness Extraction

__
TR04-030
| 9th March 2004
__

Nikolay Vereshchagin#### Kolmogorov complexity of enumerating finite sets

__
TR04-080
| 7th September 2004
__

Lance Fortnow, Troy Lee, Nikolay Vereshchagin#### Kolmogorov Complexity with Error

__
TR12-028
| 30th March 2012
__

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret#### Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

Revisions: 1

__
TR14-172
| 12th December 2014
__

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

__
TR20-099
| 6th July 2020
__

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere#### KRW Composition Theorems via Lifting

Revisions: 1

Elena Grigorescu, Akash Kumar, Karl Wimmer

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates between $0$ and $1$ at most $k$ times on every ascending chain. Such functions represent a natural generalization ... more >>>

Zeev Dvir, Avi Wigderson

A merger is a probabilistic procedure which extracts the

randomness out of any (arbitrarily correlated) set of random

variables, as long as one of them is uniform. Our main result is

an efficient, simple, optimal (to constant factors) merger, which,

for $k$ random vairables on $n$ bits each, uses a ...
more >>>

Noga Alon, Shai Gutner

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves ...
more >>>

Thomas Holenstein

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

Juraj Hromkovic

We call any consistent and sufficiently powerful formal theory that enables to algorithmically in polynomial time verify whether a text is a proof \textbf{efficiently verifiable mathematics} (ev-mathematics). We study the question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of ev-mathematics. Our main results ... more >>>

Marc Kaplan, Sophie Laplante

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

Nikolay Vereshchagin

Assume that for almost all n Kolmogorov complexity

of a string x conditional to n is less than m.

We prove that in this case

there is a program of size m+O(1) that given any sufficiently large

n outputs x.

John Hitchcock, A. Pavan, N. V. Vinodchandran

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity

extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction

more >>>

Nikolay Vereshchagin

Solovay has proven that

the minimal length of a program enumerating a set A

is upper bounded by 3 times the absolute value of the

logarithm of the

probability that a random program will enumerate A.

It is unknown whether one can replace the constant

3 by a smaller constant.

more >>>

Lance Fortnow, Troy Lee, Nikolay Vereshchagin

We introduce the study of Kolmogorov complexity with error. For a

metric d, we define C_a(x) to be the length of a shortest

program p which prints a string y such that d(x,y) \le a. We

also study a conditional version of this measure C_{a,b}(x|y)

where the task is, given ...
more >>>

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $C$ defined ... more >>>

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>