scientific article; zbMATH DE number 3597878
From MaRDI portal
zbMath0384.68046MaRDI QIDQ4164821
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Non-deterministic communication complexity with few witnesses, A remark on matrix rigidity, A note on the use of determinant for proving lower bounds on the size of linear circuits, Static-memory-hard functions, and modeling the cost of space vs. time, Local Reductions, Succinct non-interactive arguments via linear interactive proofs, Complexity of linear circuits and geometry, Kolmogorov width of discrete linear spaces: an approach to matrix rigidity, Some combinatorial-algebraic problems from complexity theory, Cumulative Space in Black-White Pebbling and Resolution, A separation between tropical matrix ranks, An algorithm twisted from generalized ADMM for multi-block separable convex minimization models, The complexity of depth-3 circuits computing symmetric Boolean functions, Matrix and tensor rigidity and \(L_p\)-approximation, Local reduction, A quadratic lower bound for three-query linear locally decodable codes over any field, The landscape of communication complexity classes, Matrix rigidity of random Toeplitz matrices, Fourier and Circulant Matrices are Not Rigid, Zero-information protocols and unambiguity in Arthur-Merlin communication, Improved bounds on the an-complexity of \(O(1)\)-linear functions, Quadratic lower bounds for algebraic branching programs and formulas, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?, New applications of the polynomial method: The cap set conjecture and beyond, \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product, The function-inversion problem: barriers and opportunities, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions, Comparison of matrix norm sparsification, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates, Local orthogonality dimension, Arithmetic circuits, structured matrices and (not so) deep learning, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, On rigid matrices and \(U\)-polynomials, Unnamed Item, Constructions of strongly regular Cayley graphs derived from weakly regular bent functions, More on average case vs approximation complexity, Size-treewidth tradeoffs for circuits computing the element distinctness function, Unnamed Item, Arithmetic circuits: the chasm at depth four gets wider, On a theorem of Razborov, On matrix rigidity and locally self-correctable codes, Parameterized low-rank binary matrix approximation, Size bounds for superconcentrators, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Min-rank conjecture for log-depth circuits, Identifying an unknown code by partial Gaussian elimination, Using elimination theory to construct rigid matrices, Matrix rigidity, Invariant and geometric aspects of algebraic complexity theory. I, Unexpected upper bounds on the complexity of some communication games, The minrank of random graphs, Parameterized Low-Rank Binary Matrix Approximation, Some structural properties of low-rank matrices related to computational complexity, Computation of best possible low degree expanders, Matrix Rigidity from the Viewpoint of Parameterized Complexity, Rigidity of a simple extended lower triangular matrix, The complexity of explicit constructions, Entropy of operators or why matrix multiplication is hard for depth-two circuits, On the complexity of matrix rank and rigidity, The computational complexity of some problems of linear algebra, Lower bounds for matrix factorization, Unnamed Item, Lower Bounds for Multiplication via Network Coding, A quadratic lower bound for algebraic branching programs, A super-quadratic lower bound for depth four arithmetic circuits, On the guessing number of shift graphs, Fourier and circulant matrices are not rigid, Efficiently Computing Data-Independent Memory-Hard Functions, On the rigidity of Vandermonde matrices, The Complexity of Satisfiability of Small Depth Circuits, Representing \((0,1)\)-matrices by Boolean circuits, Lower bounds for matrix factorization, Lower bounds in algebraic computational complexity, The computational complexity of some problems of linear algebra, Unnamed Item, Efficient Construction of Rigid Matrices Using an NP Oracle, Shallow grates, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Which problems have strongly exponential complexity?, Unifying known lower bounds via geometric complexity theory, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, The remote set problem on lattices, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Average-case rigidity lower bounds, Combinatorial PCPs with short proofs, IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
