scientific article; zbMATH DE number 7204408

DOI10.4230/LIPICS.MFCS.2017.74zbMATH Open1441.68043MaRDI QIDQ5111291FDOQ5111291

Prajakta Nimbhorkar, Meena Mahajan, Anuj Tawari

Publication date: 26 May 2020

Title of this publication is not available (Why is that?)

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

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)

Cites Work

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

Cited In (1)

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

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)