Tight bounds for blind search on the integers

DOI10.4230/LIPICS.STACS.2008.1348MaRDI QIDQ4910723zbMATH OpenOpenAlexFDO

Authors Martin Dietzfelbinger, Ingo Wegener, Philipp Woelfel, Jonathan E. Rowe

Publication date 19 March 2013

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_d02a.html

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• Tight bounds for blind search on the integers and the reals
• scientific article; zbMATH DE number 18751
• Lower bounds on fast searching
• Lower Bounds for Oblivious Near-Neighbor Search
• Herbrandizing search problems in Bounded Arithmetic
• Tight lower bounds for halfspace range searching
• Tight lower bounds for halfspace range searching
• Total search problems in bounded arithmetic and improved witnessing
• Tight bounds for the partial-sums problem
• Bounds on the size of branch-and-bound proofs for integer knapsacks

Cited in

(4)

• Oblivious Randomized Direct Search for Real-Parameter Optimization
• Precision, local search and unimodal functions
• Tight bounds for blind search on the integers and the reals
• Greedy routing in small-world networks with power-law degrees

This page was built for publication: Tight bounds for blind search on the integers

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