Derandomized Construction of Combinatorial Batch Codes
From MaRDI portal
Publication:2947886
DOI10.1007/978-3-319-22177-9_21zbMath1345.68240arXiv1502.02472OpenAlexW2963332664MaRDI QIDQ2947886
Publication date: 29 September 2015
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.02472
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Other types of codes (94B60) Randomized algorithms (68W20) Combinatorial codes (94B25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial batch codes: a lower bound and optimal constructions
- Combinatorial batch codes and transversal matroids
- Optimal batch codes: many items or low retrieval requirement
- On an extremal hypergraph problem related to combinatorial batch codes
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- The probabilistic method yields deterministic parallel algorithms
- Combinatorial batch codes
- Turán numbers and batch codes
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Batch codes and their applications
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Simulating (log c n )-wise independence in NC
- Probability Inequalities for Sums of Bounded Random Variables
- Relaxations of Hall’s Condition: Optimal batch codes with multiple queries
- On a combinatorial game
