Pages that link to "Item:Q2366719"

The following pages link to On lower bounds for read-\(k\)-times branching programs (Q2366719):

Displaying 42 items.

• A simple function that requires exponential size read-once branching programs (Q287023) (← links)
• Resource trade-offs in syntactically multilinear arithmetic circuits (Q371194) (← links)
• Limitations of incremental dynamic programming (Q517805) (← links)
• Yet harder knapsack problems (Q653327) (← links)
• Width hierarchy for \(k\)-OBDD of small width (Q748240) (← links)
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice (Q841618) (← links)
• Incremental branching programs (Q929291) (← links)
• A nondeterministic space-time tradeoff for linear codes (Q976097) (← links)
• Neither reading few bits twice nor reading illegally helps much (Q1130185) (← links)
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs (Q1275068) (← links)
• Efficient oblivious branching programs for threshold and mod functions (Q1384527) (← links)
• A lower bound on branching programs reading some bits twice (Q1392030) (← links)
• Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
• A lower bound for integer multiplication on randomized ordered read-once branching programs. (Q1426006) (← links)
• BDDs -- design, analysis, complexity, and applications. (Q1428568) (← links)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs (Q1575258) (← links)
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity (Q1604200) (← links)
• Time-space tradeoffs for branching programs (Q1604208) (← links)
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs (Q1854567) (← links)
• On multi-partition communication complexity (Q1886038) (← links)
• Top-down lower bounds for depth-three circuits (Q1904663) (← links)
• On arithmetic branching programs (Q1961372) (← links)
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs (Q2032296) (← links)
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs (Q2361671) (← links)
• Expanders and time-restricted branching programs (Q2378527) (← links)
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth (Q2408558) (← links)
• Lower bounds for restricted read-once parity branching programs (Q2503280) (← links)
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication (Q2508966) (← links)
• A hierarchy result for read-once branching programs with restricted parity nondeterminism (Q2566039) (← links)
• On the computational power of probabilistic and quantum branching program (Q2581534) (← links)
• A very simple function that requires exponential size read-once branching programs. (Q2583538) (← links)
• Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication (Q2771493) (← links)
• No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth (Q2946031) (← links)
• Branching Programs for Tree Evaluation (Q3182923) (← links)
• Finding the Median (Obliviously) with Bounded Space (Q3448777) (← links)
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae (Q3599149) (← links)
• On the hierarchy of nondeterministic branching k-programs (Q5055950) (← links)
• (Q5092470) (← links)
• A super-quadratic lower bound for depth four arithmetic circuits (Q5092474) (← links)
• Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. (Q5111240) (← links)
• (Q5121903) (← links)
• Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs (Q5136279) (← links)