Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPLEXITY LOWER BOUNDS:
Reports tagged with Complexity Lower bounds:
TR96-030 | 31st March 1996
Meera Sitharam

#### Approximation from linear spaces and applications to complexity

We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. ... more >>>

TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

#### Stable basis families and complexity lower bounds

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>

TR18-042 | 1st March 2018
Stasys Jukna

#### Incremental versus Non-Incremental Dynamic Programming

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>>

TR20-058 | 24th April 2020
Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

#### Interactive Proofs for Verifying Machine Learning

Revisions: 1

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

TR21-040 | 15th March 2021
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

#### Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

ISSN 1433-8092 | Imprint