Lower bounds for tropical circuits and dynamic programs (Q493653): Difference between revisions

@@ Property / author @@
+Stasys P. Jukna
@@ Property / author: Stasys P. Jukna / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Algorithm 97
@@ Property / describes a project that uses: Algorithm 97 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1987315863
@@ Property / OpenAlex ID: W1987315863 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.3065
@@ Property / arXiv ID: 1406.3065 / rank @@
+Normal rank
@@ Property / cites work @@
+The monotone circuit complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+Explicit construction of linear sized tolerant networks
+Normal rank
@@ Property / cites work @@
+Q4726174
@@ Property / cites work: Q4726174 / rank @@
+Normal rank
@@ Property / cites work @@
+A method for obtaining efficient lower bounds for monotone complexity
+Normal rank
@@ Property / cites work @@
+The complexity of partial derivatives
@@ Property / cites work: The complexity of partial derivatives / rank @@
+Normal rank
@@ Property / cites work @@
+On a routing problem
@@ Property / cites work: On a routing problem / rank @@
+Normal rank
@@ Property / cites work @@
+Subtraction-free complexity, cluster transformations, and spanning trees
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3782775
@@ Property / cites work: Q3782775 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of calculation of differentials and gradients
+Normal rank
@@ Property / cites work @@
+A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for Connectivity Have Depth (log n)<sup>2-o(1)</sup>
+Normal rank
@@ Property / cites work @@
+On the Parallel Evaluation of Multivariate Polynomials
+Normal rank
@@ Property / cites work @@
+Some Exact Complexity Results for Straight-Line Computations over Semirings
+Normal rank
@@ Property / cites work @@
+Ramanujan local systems on graphs
@@ Property / cites work: Ramanujan local systems on graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorics of monotone computations
@@ Property / cites work: Combinatorics of monotone computations / rank @@
+Normal rank
@@ Property / cites work @@
+Expanders and time-restricted branching programs
@@ Property / cites work: Expanders and time-restricted branching programs / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean function complexity. Advances and frontiers.
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for Connectivity Require Super-Logarithmic Depth
+Normal rank
@@ Property / cites work @@
+On the incompressibility of monotone DNFs
@@ Property / cites work: On the incompressibility of monotone DNFs / rank @@
+Normal rank
@@ Property / cites work @@
+Ramanujan graphs
@@ Property / cites work: Ramanujan graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Some remarks on Boolean sums
@@ Property / cites work: Some remarks on Boolean sums / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone switching circuits and Boolean matrix product
+Normal rank
@@ Property / cites work @@
+Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
+Normal rank
@@ Property / cites work @@
+Q5591914
@@ Property / cites work: Q5591914 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of monotone networks for Boolean matrix product
+Normal rank
@@ Property / cites work @@
+On another Boolean matrix
@@ Property / cites work: On another Boolean matrix / rank @@
+Normal rank
@@ Property / cites work @@
+Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
+Normal rank
@@ Property / cites work @@
+Lower bounds on monotone complexity of the logical permanent
+Normal rank
@@ Property / cites work @@
+A lower bound on the number of additions in monotone computations
+Normal rank
@@ Property / cites work @@
+On the depth complexity of formulas
@@ Property / cites work: On the depth complexity of formulas / rank @@
+Normal rank
@@ Property / cites work @@
+Arithmetic Circuits: A survey of recent results and open questions
+Normal rank
@@ Property / cites work @@
+A direct version of Shamir and Snir's lower bounds on monotone circuit depth
+Normal rank
@@ Property / cites work @@
+Negation can be exponentially powerful
@@ Property / cites work: Negation can be exponentially powerful / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Parallel Computation of Polynomials Using Few Processors
+Normal rank
@@ Property / cites work @@
+A Theorem on Boolean Matrices
@@ Property / cites work: A Theorem on Boolean Matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Path, Matrix, and Triangle Problems
+Normal rank