scientific article; zbMATH DE number 7204408

DOI10.4230/LIPICS.MFCS.2017.74MaRDI QIDQ5111291zbMATH OpenFDO

Authors Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

Publication date 26 May 2020

zbMATH Keywords

lower boundstropical semiringcircuitsformulas

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)

Recommendations

• \(\Sigma\Pi\Sigma\) threshold formulas
• Efficient Computation of the Maximum of the Sum of Two Sequences and Applications
• Upper bounds for the formula size of symmetric Boolean functions
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables

Cites work

• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A Theorem on Boolean Matrices
• Entropy splitting for antiblocking corners and perfect graphs
• Fredman–Komlós bounds and information theory
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Lower bounds for tropical circuits and dynamic programs
• New bounds for perfect hashing via information theory
• On a routing problem
• On the optimality of Bellman-Ford-Moore shortest path algorithm
• Perfect graphs and graph entropy: An updated survey
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Tropical complexity, Sidon sets, and dynamic programming

Cited in

(1)

• Notes on Boolean read-\(k\) and multilinear circuits

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111291)