scientific article; zbMATH DE number 3597878
From MaRDI portal
Publication:4164821
zbMath0384.68046MaRDI QIDQ4164821
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (91)
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 ⋮ Rigid matrices from rectangular PCPs ⋮ Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity ⋮ Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms ⋮ 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
This page was built for publication:
