Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NC:
Reports tagged with NC:
TR98-057 | 10th September 1998
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Motivated by the question of how to define an analog of interactive
proofs in the setting of logarithmic time- and space-bounded
computation, we study complexity classes defined in terms of
operators quantifying over oracles. We obtain new
characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ... more >>>

TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

#### Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as
polynomial size formulae and bounded width branching
programs. Caussinus et al. \cite{CMTV} considered arithmetizations of
two of these classes, #NC^1 and #BWBP. We further this study to
include arithmetization of other classes. In particular, we show that
counting paths ... more >>>

TR08-092 | 26th August 2008
Scott Aaronson, John Watrous

#### Closed Timelike Curves Make Quantum and Classical Computing Equivalent

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

TR09-024 | 26th February 2009
Raghav Kulkarni

#### On the Power of Isolation in Planar Structures

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>

TR21-179 | 8th December 2021
tatsuie tsukiji

#### Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>