Randomized OBDDs for the most significant bit of multiplication need exponential space (Q1944061): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.ipl.2010.11.013
+Normal rank
@@ Property / OpenAlex ID @@
+W1995864649
@@ Property / OpenAlex ID: W1995864649 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomization and nondeterminism are comparable for ordered read-once branching programs
+Normal rank
@@ Property / cites work @@
+Q4818848
@@ Property / cites work: Q4818848 / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for integer multiplication on randomized ordered read-once branching programs.
+Normal rank
@@ Property / cites work @@
+On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
+Normal rank
@@ Property / cites work @@
+A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication
+Normal rank
@@ Property / cites work @@
+Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
+Normal rank
@@ Property / cites work @@
+Graph-Based Algorithms for Boolean Function Manipulation
+Normal rank
@@ Property / cites work @@
+On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
+Normal rank
@@ Property / cites work @@
+On data structures and asymmetric communication complexity
+Normal rank
@@ Property / cites work @@
+Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
+Normal rank
@@ Property / cites work @@
+Branching Programs and Binary Decision Diagrams
@@ Property / cites work: Branching Programs and Binary Decision Diagrams / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds on the OBDD-size of integer multiplication via universal hashing
+Normal rank