Zobrazeno 1 - 10
of 16
pro vyhledávání: '"Mathias Bæk Tejs Knudsen"'
Publikováno v:
Discrete Applied Mathematics. 282:1-13
A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U . Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::97263f885362b4ed9f18429b3b15f03d
https://doi.org/10.1016/j.dam.2019.10.030
https://doi.org/10.1016/j.dam.2019.10.030
Autor:
Peter M. R. Rasmussen, Mikkel Thorup, Mathias Bæk Tejs Knudsen, Anders Aamand, Jakob Bæk Tejs Knudsen
Publikováno v:
Aamand, A, Knudsen, J B T, Knudsen, M B T, Rasmussen, P M R & Thorup, M 2020, Fast hashing with strong concentration bounds . in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds), STOC 2020-Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing . Association for Computing Machinery, Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 1265-1278, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States, 22/06/2020 . https://doi.org/10.1145/3357713.3384259
STOC
STOC
Previous work on tabulation hashing by Patrascu and Thorup from STOC'11 on simple tabulation and from SODA'13 on twisted tabulation offered Chernoff-style concentration bounds on hash based sums, e.g., the number of balls/keys hashing to a given bin,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b32f2d2ca37fd4e9fbcbde8c0a5da07d
http://arxiv.org/abs/1905.00369
http://arxiv.org/abs/1905.00369
Publikováno v:
University of Copenhagen
Hashing is a basic tool for dimensionality reduction employed in several aspects of machine learning. However, the perfomance analysis is often carried out under the abstract assumption that a truly random unit cost hash function is used, without con
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c6d8d78ca15506ff8da0755251d04a00
http://arxiv.org/abs/1711.08797
http://arxiv.org/abs/1711.08797
Publikováno v:
FOCS
We consider the Similarity Sketching problem: Given a universe [u] = {0,..., u-1} we want a random function S mapping subsets A of [u] into vectors S(A) of size t, such that similarity is preserved. More precisely: Given subsets A,B of [u], define X_
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a99b196e4e424d773c6a9ad69198bd41
https://doi.org/10.1109/focs.2017.67
https://doi.org/10.1109/focs.2017.67
Publikováno v:
STOC
In this paper, we consider the problem of finding a cycle of length $2k$ (a $C_{2k}$) in an undirected graph $G$ with $n$ nodes and $m$ edges for constant $k\ge2$. A classic result by Bondy and Simonovits [J.Comb.Th.'74] implies that if $m \ge100k n^
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b358b600f7a0013a9730a8d68a032cc
https://doi.org/10.1145/3055399.3055459
https://doi.org/10.1145/3055399.3055459
Autor:
Mathias Bæk Tejs Knudsen
Publikováno v:
FOCS
We consider the hash function $h(x) = ((ax+b) \bmod p) \bmod n$ where $a,b$ are chosen uniformly at random from $\{0,1,\ldots,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expect
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b0066a725dd166372b07348f8c1e0e7
http://arxiv.org/abs/1706.02783
http://arxiv.org/abs/1706.02783
Publikováno v:
String Processing and Information Retrieval ISBN: 9783319460482
A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a str
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4108f222b391e38655d5d68b11649f48
https://doi.org/10.1007/978-3-319-46049-9_9
https://doi.org/10.1007/978-3-319-46049-9_9
Publikováno v:
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms.
The power of two choices is a classic paradigm for load balancing when assigning $m$ balls to $n$ bins. When placing a ball, we pick two bins according to two hash functions $h_0$ and $h_1$, and place the ball in the least loaded bin. Assuming fully
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::75b0b5310a02d1244ea689acc584ab3d
https://doi.org/10.1137/1.9781611974331.ch111
https://doi.org/10.1137/1.9781611974331.ch111
Publikováno v:
FOCS
In this paper we analyze a hash function for $k$-partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin~[FOC
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::36a795909fd9a1c5292c9df1ed5ccf55
https://doi.org/10.1109/focs.2015.83
https://doi.org/10.1109/focs.2015.83