scientific article; zbMATH DE number 7250155

DOI10.4230/LIPIcs.CCC.2018.15zbMath1441.68071MaRDI QIDQ5121903

Toniann Pitassi, Venkatesh Medabalimi, Jeff Edmonds

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

branching programsfunction compositiontime-space tradeoffssemantic read-oncetree evaluation problem

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• A nondeterministic space-time tradeoff for linear codes
• Storage requirements for deterministic polynomial time recognizable languages
• Communication complexity towards lower bounds on circuit depth
• Time-space tradeoffs for branching programs
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• On lower bounds for read-\(k\)-times branching programs
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Pebbles and Branching Programs for Tree Evaluation
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Time-space lower bounds for satisfiability
• Time-space trade-off lower bounds for randomized computation of decision problems
• A note on read-$k$ times branching programs
• The Shrinkage Exponent of de Morgan Formulas is 2
• Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
• Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs
• Toward better formula lower bounds
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

This page was built for publication: