scientific article; zbMATH DE number 1775407

MaRDI QIDQ4542540zbMATH OpenFDO

Authors Dima Grigoriev

Publication date 1 August 2002

zbMATH Keywords

randomized computation treesKNAPSACK problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Randomized complexity lower bound for arrangements and polyhedra
• Lower space bounds for randomized computation
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• On randomized semi-algebraic test complexity
• scientific article; zbMATH DE number 1559524

Cited in

(25)

• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• Improved lower bounds on the randomized complexity of graph properties
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• Data Structures Lower Bounds and Popular Conjectures
• Lower space bounds for randomized computation
• scientific article; zbMATH DE number 1559524 (Why is no real title available?)
• Complexity bounds for zero-test algorithms
• The value of help bits in randomized and average-case complexity
• On lower bounds for the time of computation
• scientific article; zbMATH DE number 1390051 (Why is no real title available?)
• On the complexity of finite random functions
• Uniform Derandomization from Pathetic Lower Bounds
• On randomized sketching algorithms and the Tracy-Widom law
• The randomized complexity of initial value problems
• A tight lower bound for computing the diameter of a 3D convex polytope
• scientific article; zbMATH DE number 697824 (Why is no real title available?)
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• Complexity lower bounds for approximation algebraic computation trees
• Uniform derandomization from pathetic lower bounds
• Lower Bounds for Coin-Weighing Problems
• A lower bound for randomized list update algorithms

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