scientific article; zbMATH DE number 6820278

DOI10.4230/LIPICS.ICALP.2016.89MaRDI QIDQ4598229zbMATH OpenFDO

Authors Amir Yehudayoff, Pavel Hrubeš

Publication date 19 December 2017

zbMATH Keywords

isoperimetrycommunication complexityseparationsmonotone computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• On the complexity of isoperimetric problems on trees
• On the complexity of polytope isomorphism problems
• Isoperimetric functions of groups and computational complexity of the word problem
• scientific article
• scientific article; zbMATH DE number 1805959
• scientific article; zbMATH DE number 1929952
• The complexity of the isomorphism problem for computable projective planes
• The computational complexity of distance functions of two-dimensional domains
• Complexity of geodesics on 2-dimensional ideal polyhedra and isotopies

Cited in

(10)

• Monotone classes beyond VNP
• Computing the isoperimetric number of a graph
• The one-visibility localization game
• scientific article; zbMATH DE number 7561311 (Why is no real title available?)
• Monotone arithmetic complexity of graph homomorphism polynomials
• Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem
• Escaping offline searchers and isoperimetric theorems
• A quadratic lower bound for algebraic branching programs
• Incremental versus non-incremental dynamic programming
• Quadratic lower bounds for algebraic branching programs and formulas

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 Q4598229)