Document

**Published in:** LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphabets.
We show that this barrier appears in many variations throughout the algorithmic literature by introducing a framework of Colored Walk problems. These yield fine-grained equivalent formulations of the NFA Acceptance problem as problems concerning detection of an s-t-walk with a prescribed color sequence in a given edge- or node-colored graph. For NFA Acceptance on sparse NFAs (or equivalently, Colored Walk in sparse graphs), a tight lower bound under the Strong Exponential Time Hypothesis has been rediscovered several times in recent years. We show that our hardness hypothesis, which concerns dense NFAs, has several interesting implications:
- It gives a tight lower bound for Context-Free Language Reachability. This proves conditional optimality for the class of 2NPDA-complete problems, explaining the cubic bottleneck of interprocedural program analysis.
- It gives a tight (n+nm^{1/3})^{1-o(1)} lower bound for the Word Break problem on strings of length n and dictionaries of total size m.
- It implies the popular OMv hypothesis. Since the NFA acceptance problem is a static (i.e., non-dynamic) problem, this provides a static reason for the hardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve several interesting barriers. Conversely, a refutation of the NFA Acceptance hypothesis may lead the way to attacking the current barriers observed for Context-Free Language Reachability, the Word Break problem and the growing list of dynamic problems proven hard under the OMv hypothesis.

Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ITCS.2024.22, author = {Bringmann, Karl and Gr{\o}nlund, Allan and K\"{u}nnemann, Marvin and Larsen, Kasper Green}, title = {{The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {22:1--22:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.22}, URN = {urn:nbn:de:0030-drops-195500}, doi = {10.4230/LIPIcs.ITCS.2024.22}, annote = {Keywords: Fine-grained complexity theory, non-deterministic finite automata} }

Document

**Published in:** LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

We study mix-nets in the context of cryptocurrencies. Here we have many computationally weak shufflers that speak one after another and want to joinlty shuffle a list of ciphertexts (c₁, … , c_n). Each shuffler can only permute k << n ciphertexts at a time. An adversary A can track some of the ciphertexts and adaptively corrupt some of the shufflers.
We present a simple protocol for shuffling the list of ciphertexts efficiently. The main technical contribution of this work is to prove that our simple shuffling strategy does indeed provide good anonymity guarantees and at the same time terminates quickly.
Our shuffling algorithm provides a strict improvement over the current shuffling strategy in Ethereum’s block proposer elections. Our algorithm is secure against a stronger adversary, provides provable security guarantees, and is comparably in efficiency to the current approach.

Kasper Green Larsen, Maciej Obremski, and Mark Simkin. Distributed Shuffling in Adversarial Environments. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.ITC.2023.10, author = {Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark}, title = {{Distributed Shuffling in Adversarial Environments}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.10}, URN = {urn:nbn:de:0030-drops-183385}, doi = {10.4230/LIPIcs.ITC.2023.10}, annote = {Keywords: Distributed Computing, Shuffling} }

Document

**Published in:** LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

In colored range counting (CRC), the input is a set of points where each point is assigned a "color" (or a "category") and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data.
However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.

Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen. Hierarchical Categories in Colored Searching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2022.25, author = {Afshani, Peyman and Killmann, Rasmus and Larsen, Kasper Green}, title = {{Hierarchical Categories in Colored Searching}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.25}, URN = {urn:nbn:de:0030-drops-173100}, doi = {10.4230/LIPIcs.ISAAC.2022.25}, annote = {Keywords: Categorical Data, Computational Geometry} }

Document

**Published in:** LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on their performance. The question of whether the JL method is optimal for practical measures of distortion was recently raised in [Yair Bartal et al., 2019] (NeurIPS'19). They provided upper bounds on its quality for a wide range of practical measures and showed that indeed these are best possible in many cases. Yet, some of the most important cases, including the fundamental case of average distortion were left open. In particular, they show that the JL transform has 1+ε average distortion for embedding into k-dimensional Euclidean space, where k = O(1/ε²), and for more general q-norms of distortion, k = O(max{1/ε²,q/ε}), whereas tight lower bounds were established only for large values of q via reduction to the worst case.
In this paper we prove that these bounds are best possible for any dimensionality reduction method, for any 1 ≤ q ≤ O((log (2ε² n))/ε) and ε ≥ 1/(√n), where n is the size of the subset of Euclidean space.
Our results also imply that the JL method is optimal for various distortion measures commonly used in practice, such as stress, energy and relative error. We prove that if any of these measures is bounded by ε then k = Ω(1/ε²), for any ε ≥ 1/(√n), matching the upper bounds of [Yair Bartal et al., 2019] and extending their tightness results for the full range moment analysis.
Our results may indicate that the JL dimensionality reduction method should be considered more often in practical applications, and the bounds we provide for its quality should be served as a measure for comparison when evaluating the performance of other methods and heuristics.

Yair Bartal, Ora Nova Fandina, and Kasper Green Larsen. Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bartal_et_al:LIPIcs.SoCG.2022.13, author = {Bartal, Yair and Fandina, Ora Nova and Larsen, Kasper Green}, title = {{Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.13}, URN = {urn:nbn:de:0030-drops-160219}, doi = {10.4230/LIPIcs.SoCG.2022.13}, annote = {Keywords: average distortion, practical dimensionality reduction, JL transform} }

Document

**Published in:** LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q.
Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t.
When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size.
We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l.
BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.

Ivan Bjerre Damgård, Kasper Green Larsen, and Sophia Yakoubov. Broadcast Secret-Sharing, Bounds and Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2021.10, author = {Damg\r{a}rd, Ivan Bjerre and Larsen, Kasper Green and Yakoubov, Sophia}, title = {{Broadcast Secret-Sharing, Bounds and Applications}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.10}, URN = {urn:nbn:de:0030-drops-143299}, doi = {10.4230/LIPIcs.ITC.2021.10}, annote = {Keywords: Secret-Sharing, Ad-hoc Threshold Encryption} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, very recently proved by Harvey and van der Hoeven (2019), shows that two n-bit numbers can be multiplied via a boolean circuit of size O(n lg n). In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size Omega(n lg n), thus almost completely settling the complexity of multiplication circuits. We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant’s conjectures.

Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, and Kasper Green Larsen. Lower Bounds for Multiplication via Network Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ICALP.2019.10, author = {Afshani, Peyman and Freksen, Casper Benjamin and Kamma, Lior and Larsen, Kasper Green}, title = {{Lower Bounds for Multiplication via Network Coding}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {10:1--10:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.10}, URN = {urn:nbn:de:0030-drops-105861}, doi = {10.4230/LIPIcs.ICALP.2019.10}, annote = {Keywords: Circuit Complexity, Circuit Lower Bounds, Multiplication, Network Coding, Fine-Grained Complexity} }

Document

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

In discrepancy minimization problems, we are given a family of sets S = {S_1,...,S_m}, with each S_i in S a subset of some universe U = {u_1,...,u_n} of n elements. The goal is to find a coloring chi : U -> {-1,+1} of the elements of U such that each set S in S is colored as evenly as possible. Two classic measures of discrepancy are l_infty-discrepancy defined as disc_infty(S,chi):=max_{S in S} | sum_{u_i in S} chi(u_i) | and l_2-discrepancy defined as disc_2(S,chi):=sqrt{(1/|S|) sum_{S in S} (sum_{u_i in S} chi(u_i))^2}. Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring chi such that disc_infty(S,chi) = O(lg n * herdisc_infty(S)) where herdisc_infty(S) is the hereditary l_infty-discrepancy of S. We complement his work by giving a clean and simple O((m+n)n^2) time algorithm for finding a coloring chi such disc_2(S,chi) = O(sqrt{lg n} * herdisc_2(S)) where herdisc_2(S) is the hereditary l_2-discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc_infty and herdisc_2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.

Kasper Green Larsen. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{larsen:LIPIcs.STACS.2019.48, author = {Larsen, Kasper Green}, title = {{Constructive Discrepancy Minimization with Hereditary L2 Guarantees}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {48:1--48:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.48}, URN = {urn:nbn:de:0030-drops-102878}, doi = {10.4230/LIPIcs.STACS.2019.48}, annote = {Keywords: Discrepancy, Hereditary Discrepancy, Combinatorics, Computational Geometry} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length m and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an O(m^{1/2-epsilon}) time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.

Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, and Tatiana Starikovskaya. Upper and Lower Bounds for Dynamic Data Structures on Strings. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{clifford_et_al:LIPIcs.STACS.2018.22, author = {Clifford, Rapha\"{e}l and Gr{\o}nlund, Allan and Larsen, Kasper Green and Starikovskaya, Tatiana}, title = {{Upper and Lower Bounds for Dynamic Data Structures on Strings}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.22}, URN = {urn:nbn:de:0030-drops-85088}, doi = {10.4230/LIPIcs.STACS.2018.22}, annote = {Keywords: exact pattern matching with wildcards, hamming distance, inner product, conditional lower bounds} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N,
vectors X \subset R^n, there exists a mapping f : X --> R^m such that f(X) preserves all pairwise distances between vectors in X to within(1 ± \eps) if m = O(\eps^{-2} lg N). Much effort has gone into developing
fast embedding algorithms, with the Fast Johnson-Lindenstrauss
transform of Ailon and Chazelle being one of the most well-known
techniques. The current fastest algorithm that yields the optimal m =
O(\eps{-2}lg N) dimensions has an embedding time of O(n lg n + \eps^{-2} lg^3 N). An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random m times n Toeplitz matrix for the
embedding. Using Fast Fourier Transform, the embedding of a vector can
then be computed in O(n lg m) time. The big question is of course
whether m = O(\eps^{-2} lg N) dimensions suffice for this technique. If
so, this would end a decades long quest to obtain faster and faster
Johnson-Lindenstrauss transforms. The current best analysis of the
embedding of Hinrichs and Vybíral shows that m = O(\eps^{-2} lg^2 N)
dimensions suffice. The main result of this paper, is a proof that
this analysis unfortunately cannot be tightened any further, i.e.,
there exists a set of N vectors requiring m = \Omega(\eps^{-2} lg^2 N)
for the Toeplitz approach to work.

Casper Benjamin Freksen and Kasper Green Larsen. On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{freksen_et_al:LIPIcs.ISAAC.2017.32, author = {Freksen, Casper Benjamin and Larsen, Kasper Green}, title = {{On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {32:1--32:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.32}, URN = {urn:nbn:de:0030-drops-82540}, doi = {10.4230/LIPIcs.ISAAC.2017.32}, annote = {Keywords: dimensionality reduction, Johnson-Lindenstrauss, Toeplitz matrices} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

For any n > 1, 0 < epsilon < 1/2, and N > n^C for some constant C > 0, we show the existence of an N-point subset X of l_2^n such that any linear map from X to l_2^m with distortion at most 1 + epsilon must have m = Omega(min{n, epsilon^{-2}*lg(N)). This improves a lower bound of Alon [Alon, Discre. Mathem., 1999], in the linear setting, by a lg(1/epsilon) factor. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, Contem. Mathem., 1984].

Kasper Green Larsen and Jelani Nelson. The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 82:1-82:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.ICALP.2016.82, author = {Larsen, Kasper Green and Nelson, Jelani}, title = {{The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {82:1--82:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.82}, URN = {urn:nbn:de:0030-drops-62032}, doi = {10.4230/LIPIcs.ICALP.2016.82}, annote = {Keywords: dimensionality reduction, lower bounds, Johnson-Lindenstrauss} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

In the orthogonal range reporting problem, we are to preprocess a set of n points with integer coordinates on a UxU grid. The goal is to support reporting all k points inside an axis-aligned query rectangle. This is one of the most fundamental data structure problems in databases and computational geometry. Despite the importance of the problem its complexity remains unresolved in the word-RAM.
On the upper bound side, three best tradeoffs exist, all derived by reducing range reporting to a ball-inheritance problem. Ball-inheritance is a problem that essentially encapsulates all previous attempts at solving range reporting in the word-RAM. In this paper we make progress towards closing the gap between the upper and lower bounds for range reporting by proving cell probe lower bounds for ball-inheritance. Our lower bounds are tight for a large range of parameters, excluding any further progress for range reporting using the ball-inheritance reduction.

Allan Grønlund and Kasper Green Larsen. Towards Tight Lower Bounds for Range Reporting on the RAM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 92:1-92:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grnlund_et_al:LIPIcs.ICALP.2016.92, author = {Gr{\o}nlund, Allan and Larsen, Kasper Green}, title = {{Towards Tight Lower Bounds for Range Reporting on the RAM}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {92:1--92:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.92}, URN = {urn:nbn:de:0030-drops-61936}, doi = {10.4230/LIPIcs.ICALP.2016.92}, annote = {Keywords: Data Structures, Lower Bounds, Cell Probe Model, Range Reporting} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

A mode of a multiset S is an element a in S of maximum multiplicity;
that is, a occurs at least as frequently as any other element in S.
Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n) loglog n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n / log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) by sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n^(1-1/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(1-1/d^2)) time).

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson. Linear-Space Data Structures for Range Mode Query in Arrays. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 290-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2012.290, author = {Chan, Timothy M. and Durocher, Stephane and Larsen, Kasper Green and Morrison, Jason and Wilkinson, Bryan T.}, title = {{Linear-Space Data Structures for Range Mode Query in Arrays}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {290--301}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.290}, URN = {urn:nbn:de:0030-drops-34254}, doi = {10.4230/LIPIcs.STACS.2012.290}, annote = {Keywords: mode, range query, data structure, linear space, array} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail