Klee's measure problem made oblivious

DOI10.1007/978-3-031-20624-5_8OpenAlexW4312678375MaRDI QIDQ6109000

Thore Thießen, Jan Vahrenhold

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-20624-5_8

zbMATH Keywords

Klee's measure problemoblivious RAMdata-oblivious algorithmsdata-oblivious divide-and-conquer algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Well-separated pair decomposition in linear time?
• A (slightly) faster algorithm for Klee's measure problem
• Sorting in \(c \log n\) parallel steps
• Perfectly secure oblivious parallel RAM
• Yes, there is an oblivious RAM lower bound!
• OptORAMa: optimal oblivious RAM
• Can the Measure of ∪ n 1 [ a i , b i be Computed in Less Than O(n logn) Steps?]
• New Upper Bounds in Klee’s Measure Problem
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Software protection and simulation on oblivious RAMs
• Can We Overcome the n log n Barrier for Oblivious Sorting?
• Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions.

This page was built for publication: Klee's measure problem made oblivious