Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR17-088 | 10th May 2017
Elena Grigorescu, Akash Kumar, Karl Wimmer

K-Monotonicity is Not Testable on the Hypercube

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

TR08-058 | 1st June 2008
Zeev Dvir, Avi Wigderson

Kakeya sets, new mergers and old extractors

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

TR08-066 | 16th July 2008
Noga Alon, Shai Gutner

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

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

TR04-102 | 20th October 2004
Thomas Holenstein

Key Agreement from Weak Bit Agreement

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

TR08-109 | 10th November 2008
Marc Kaplan, Sophie Laplante

Kolmogorov complexity and combinatorial methods in communication complexity

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

TR01-086 | 29th October 2001
Nikolay Vereshchagin

Kolmogorov Complexity Conditional to Large Integers

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.

more >>>

TR09-071 | 1st September 2009
John Hitchcock, A. Pavan, Vinodchandran Variyam

Kolmogorov Complexity in Randomness Extraction

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

TR04-030 | 9th March 2004
Nikolay Vereshchagin

Kolmogorov complexity of enumerating finite sets

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

TR04-080 | 7th September 2004
Lance Fortnow, Troy Lee, Nikolay Vereshchagin

Kolmogorov Complexity with Error

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

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

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

TR14-172 | 12th December 2014
Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

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

ISSN 1433-8092 | Imprint