Graph-theoretic properties in computational complexity

DOI10.1016/S0022-0000(76)80041-4zbMath0354.68071MaRDI QIDQ1236886

Leslie G. Valiant

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01)

Related Items (27)

Multi-processor scheduling and expanders ⋮ Recursive construction for 3-regular expanders ⋮ Eigenvalues and expanders ⋮ Lower Bounds for the Size of Nondeterministic Circuits ⋮ On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines ⋮ Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors ⋮ Time-space tradeoffs for computing functions, using connectivity properties of their circuits ⋮ Unnamed Item ⋮ Expander graphs and their applications ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Superconcentrators of depth 2 ⋮ Matrix rigidity ⋮ Trade-offs between communication and space ⋮ Reductions for monotone Boolean circuits ⋮ Highly symmetric expanders ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ On 3-pushdown graphs with large separators ⋮ OptORAMa: Optimal oblivious RAM ⋮ On the minimum depth of circuits with linear number of wires encoding good codes ⋮ A note on a construction of Margulis ⋮ A note on time-space tradeoffs for computing continuous functions ⋮ On Negations in Boolean Networks ⋮ Hamiltonian paths in Cayley graphs ⋮ Size-space tradeoffs for oblivious computations ⋮ The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms ⋮ Diameters and Eigenvalues ⋮ OptORAMa: optimal oblivious RAM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Graph-theoretic properties in computational complexity