scientific article; zbMATH DE number 3566171

MaRDI QIDQ4138137zbMATH OpenFDO

Authors Leslie G. Valiant

Publication date 1975

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(16)

• Size-space tradeoffs for oblivious computations
• The complexity of testing whether a graph is a superconcentrator
• Size bounds for superconcentrators
• Lower bounds for matrix factorization
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Space bounds for a game on graphs
• Lower bounds for matrix factorization
• A super-quadratic lower bound for depth four arithmetic circuits
• Rounds versus time for the two person pebble game (extended abstract)
• On the minimum depth of circuits with linear number of wires encoding good codes
• Determinants vs. algebraic branching programs
• Lower bounds for planar arithmetic circuits
• Determinants vs. algebraic branching programs
• Lower bounds for planar arithmetic circuits
• Efficient polynomial identity testing over nonassociative algebras
• Smaller superconcentrators of density 28

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4138137)