Some combinatorial-algebraic problems from complexity theory
type: Item
instance of: scholarly article
title: Some combinatorial-algebraic problems from complexity theory
zbMATH Open document ID: 0824.68053
DOI: 10.1016/0012-365X(94)00115-Y
author: Pavel Pudlák
author: Vojtěch Rödl
published in: Discrete Mathematics
publication date: 1995-02-13T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 722493
zbMATH Keywords: complexity of computations
zbMATH Keywords: branching program complexity
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Linear Circuits over $\operatorname{GF}(2)$
cites work: A counterexample to the rank-coloring conjecture
cites work: Q4324358
cites work: Systems of distinct representatives and linear algebra
cites work: Q4133994
cites work: Q4146667
cites work: Maximum Rank of Powers of a Matrix of a Given Pattern
cites work: Communication in bounded depth circuits
cites work: A combinatorial approach to complexity
cites work: Modified ranks of tensors and the size of circuits
cites work: Q3990226
cites work: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
cites work: Applications of matrix methods to the theory of lower bounds in computational complexity
cites work: Q4164821
cites work: Lower Bounds for Approximation by Nonlinear Manifolds
cites work: Q3762226
Wikidata QID: Q127549018
full work available at URL: 0012-365x(94)00115-y
OpenAlex ID: W1992906573
description: scientific article; zbMATH DE number 722493