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

__
TR21-100
| 11th July 2021
__

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh#### Karchmer-Wigderson Games for Hazard-free Computation

Revisions: 1

__
TR21-096
| 8th July 2021
__

Boaz Menuhin, Moni Naor#### Keep That Card in Mind: Card Guessing with Limited Memory

__
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

__
TR23-123
| 21st August 2023
__

Noam Mazor#### Key-Agreement with Perfect Completeness from Random Oracles

__
TR24-055
| 12th March 2024
__

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass#### Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-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

__
TR22-127
| 12th September 2022
__

Eric Allender, Shuichi Hirahara, Harsha Tirumala#### Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 2

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

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games.

Using this game, we ... more >>>

Boaz Menuhin, Moni Naor

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then ... 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 >>>

Noam Mazor

In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a ... more >>>

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.

Roughly speaking, 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 >>>

Eric Allender, Shuichi Hirahara, Harsha Tirumala

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... 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 >>>