Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALTERNATION:
Reports tagged with alternation:
TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

#### Sharply Bounded Alternation within P

We define the sharply bounded hierarchy, SBHQL, a hierarchy of
classes within P, using quasilinear-time computation and
quantification over values of length log n. It generalizes the
limited nondeterminism hierarchy introduced by Buss and Goldsmith,
while retaining the invariance properties. The new hierarchy has
several alternative characterizations.

We define ... more >>>

TR08-076 | 17th June 2008
Ryan Williams

#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

TR17-192 | 15th December 2017
Krishnamoorthy Dinesh, Jayalal Sarma

Revisions: 1

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>> TR18-152 | 30th August 2018 Krishnamoorthy Dinesh, Jayalal Sarma #### Sensitivity, Affine Transforms and Quantum Communication Complexity In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function$f:\mathbb{F}_2^n \to \{0,1\}$, and$A = Mx+b$for$M \in \mathbb{F}_2^{n \times n}$and$b \in \mathbb{F}_2^n\$, the result of the ... more >>>

ISSN 1433-8092 | Imprint