3 papers
cs.DS2019
Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
Martin Dietzfelbinger, Stefan Walzer
In this paper we identify a new class of sparse near-quadratic random Boolean matrices that have full row rank over with high probability and can be transfor…
cs.DS2019
Dense Peelable Random Uniform Hypergraphs
Martin Dietzfelbinger, Stefan Walzer
We describe a new family of -uniform hypergraphs with independent random edges. The hypergraphs have a high probability of being peelable, i.e. to admit no sub-hypergraph of min…
cs.DS2017
Dynamic Space Efficient Hashing
Tobias Maier, Peter Sanders
We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound…