Tight Bounds on Oblivious Chaining

DOI10.1137/S0097539792230277MaRDI QIDQ4327421zbMATH OpenFDO

Authors Shiva Chaudhuri

Publication date 6 April 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539792230277

zbMATH Keywords

chainingprefix graphsweak superconcentrators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Lower bounds for oblivious data structures
• Lower Bounds for Oblivious Transfer Reductions
• Tight bounds for oblivious routing in the hypercube
• scientific article; zbMATH DE number 861443
• Oblivious tight compaction in \(O(n)\) time with smaller constant
• Strong Conditional Oblivious Transfer and Computing on Intervals
• Oblivious bounds on the probability of boolean functions
• On oblivious branching programs of linear length
• scientific article; zbMATH DE number 17548
• Efficient oblivious branching programs for threshold and mod functions

Cited in

(1)

• The complexity of parallel prefix problems on small domains

This page was built for publication: Tight Bounds on Oblivious Chaining

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