Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DIAGONALIZATION:
Reports tagged with diagonalization:
TR00-056 | 20th July 2000
Oded Goldreich, Avi Wigderson

#### On Pseudorandomness with respect to Deterministic Observers.

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

TR04-018 | 24th January 2004
Jan Krajicek

#### Diagonalization in proof complexity

We study the diagonalization in the context of proof
complexity. We prove that at least one of the
following three conjectures is true:

1. There is a boolean function computable in E
that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>

TR06-051 | 8th April 2006
Alan Nash, Russell Impagliazzo, Jeff Remmel

#### Infinitely-Often Universal Languages and Diagonalization

Diagonalization is a powerful technique in recursion theory and in
computational complexity \cite{For00}. The limits of this technique are
not clear. On the one hand, many people argue that conflicting
relativizations mean a complexity question cannot be resolved using only
diagonalization. On the other hand, it is not clear that ... more >>>

TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

#### Unconditional Lower Bounds against Advice

We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$
\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$
\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$
\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>> TR13-063 | 19th April 2013 Dung Nguyen, Alan Selman #### Non-autoreducible Sets for NEXP We investigate autoreducibility properties of complete sets for$\cNEXP$under different polynomial reductions. Specifically, we show under some polynomial reductions that there is are complete sets for$\cNEXP$that are not autoreducible. We obtain the following results: - There is a$\reduction{p}{tt}$-complete set for$\cNEXP$that is not$\reduction{p}{btt}$-autoreducible. more >>> TR15-174 | 18th October 2015 Dmitry Itsykson, Alexander Knop, Dmitry Sokolov #### Complexity of distributions and average-case hardness We address a natural question in average-case complexity: does there exist a language$L$such that for all easy distributions$D$the distributional problem$(L, D)$is easy on the average while there exists some more hard distribution$D'$such that$(L, D')$is hard on the average? We consider ... more >>> TR21-138 | 23rd September 2021 Rahul Santhanam, Iddo Tzameret #### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally. We give an explicit sequence of CNF formulas$\{\phi_n\}$such that VNP$\neq\$VP iff there are ... more >>>

TR23-002 | 5th January 2023
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

#### Diagonalization Games

Revisions: 2

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... more >>>

ISSN 1433-8092 | Imprint