No label defined (Q4612482)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7009617

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7009617

Statements

scholarly article

0 references

0 references

0 references

Michael A. Forbes

0 references

Theory of Computing

0 references

publication date

31 January 2019

0 references

zbMATH Keywords

algebraic circuits

0 references

lower bounds

0 references

derandomization

0 references

polynomial identity testing

0 references

barriers

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.4086/toc.2018.v014a018

0 references

Open Problems in Mathematics

0 references

0 references

FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

0 references

Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

0 references

Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits

0 references

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

Non-commutative arithmetic circuits: depth reduction and size lower bounds

0 references

The monotone circuit complexity of Boolean functions

0 references

Simple Constructions of Almost k-wise Independent Random Variables

0 references

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

The complexity of partial derivatives

0 references

Algebraic independence and blackbox identity testing

0 references

On computing the determinant in small parallel time using a small number of processors

0 references

Explicit Tensors

0 references

Generalized matrix completion and algebraic natural proofs

0 references

On Algebraic Branching Programs of Small Width

0 references

Completeness and reduction in algebraic complexity theory

0 references

0 references

Learning algorithms from natural proofs

0 references

Almost-natural proofs

0 references

A probabilistic remark on algebraic program testing

0 references

Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits

0 references

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

0 references

Bipartite perfect matching is in quasi-NC

0 references

Dimension Expanders via Rank Condensers

0 references

Hitting sets for multilinear read-once algebraic branching programs, in any order

0 references

On identity testing of tensors, low-rank recovery and compressed sensing

0 references

Proof Complexity Lower Bounds from Algebraic Circuit Complexity

0 references

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

0 references

Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

Deterministic extractors for affine sources over large fields

0 references

Unifying known lower bounds via geometric complexity theory

0 references

Boundaries of VP and VNP

0 references

Approaching the Chasm at Depth Four

0 references

Arithmetic Circuits: A Chasm at Depth 3

0 references

Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

0 references

Deterministic identity testing for sum of read-once oblivious arithmetic branching programs

0 references

Linear matroid intersection is in quasi-NC

0 references

On the Computational Complexity of Algorithms

0 references

A Pseudorandom Generator from any One-way Function

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

0 references

Turing machines that take advice

0 references

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

0 references

Blackbox Polynomial Identity Testing for Depth 3 Circuits

0 references

Arithmetic circuits: the chasm at depth four gets wider

0 references

Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds

0 references

On the Power of Homogeneous Depth 4 Arithmetic Circuits

0 references

Algebraic methods for interactive proof systems

0 references

0 references

Pseudorandom Generators for Polynomial Threshold Functions

0 references

Small-Bias Probability Spaces: Efficient Constructions and Applications

0 references

Number-theoretic constructions of efficient pseudo-random functions

0 references

Pseudorandom bits for constant depth circuits

0 references

Lower bounds on arithmetic circuits via partial derivatives

0 references

Subexponential size hitting sets for bounded depth multilinear formulas

0 references

0 references

Multi-linear formulas for permanent and determinant are of super-polynomial size

0 references

0 references

Balancing syntactically multilinear arithmetic circuits

0 references

Lower bounds and separations for constant depth multilinear circuits

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

0 references

Progress on Polynomial Identity Testing - II

0 references

Progress on Polynomial Identity Testing-II

0 references

An Almost Optimal Rank Bound for Depth-3 Identities

0 references

Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter

0 references

From sylvester-gallai configurations to rank bounds

0 references

Fast Probabilistic Algorithms for Verification of Polynomial Identities

0 references

Read-once polynomial identity testing

0 references

Arithmetic Circuits: A survey of recent results and open questions

0 references

Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten

0 references

The gap between monotone and non-monotone circuit complexity is exponential

0 references

Improved bounds for reduction to depth 4 and depth 3

0 references

Fast Parallel Computation of Polynomials Using Few Processors

0 references

Nonuniform ACC Circuit Lower Bounds

0 references

Natural Proofs versus Derandomization

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.4086/toc.2018.v014a018

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4612482

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q4612482&oldid=36466178"