scientific article; zbMATH DE number 7204408

DOI10.4230/LIPIcs.MFCS.2017.74zbMath1441.68043MaRDI QIDQ5111291

Prajakta Nimbhorkar, Meena Mahajan, Anuj Tawari

Publication date: 26 May 2020

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

zbMATH Keywords

lower boundscircuitstropical semiringformulas

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the optimality of Bellman-Ford-Moore shortest path algorithm
• Lower bounds for tropical circuits and dynamic programs
• Entropy splitting for antiblocking corners and perfect graphs
• New bounds for perfect hashing via information theory
• Tropical Complexity, Sidon Sets, and Dynamic Programming
• On a routing problem
• A Dynamic Programming Approach to Sequencing Problems
• Fredman–Komlós bounds and information theory
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• A Theorem on Boolean Matrices

This page was built for publication: