Zobrazeno 1 - 10
of 13
pro vyhledávání: '"Theory of computation → Lower bounds and information complexity"'
Autor:
Block, Alexander R., Blocki, Jeremiah, Cheng, Kuan, Grigorescu, Elena, Li, Xin, Zheng, Yu, Zhu, Minshen
Locally Decodable Codes (LDCs) are error-correcting codes C:Σⁿ → Σ^m, encoding messages in Σⁿ to codewords in Σ^m, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, y
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::62b69640472ce55921a3b07bb90626ee
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many streaming problems, both relaxations must be employed simultaneously, to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b34bca8b1cf867664c8fa13e2c733d5
A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence s ∈ {0,1}^{≤ n}, and one chooses a set of queries y ∈ {0,1}^𝒪(n) and receives d(s,y) for a distance function
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cbcd5b4c5601f4230aeb5a1e5d7c5c84
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size $k$ allows for algorithms in the Adjacency List (AL) streaming mode
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5993c02b88771f0a06417b6281a1f3d4
Autor:
Khanna, Sanjeev, Konrad, Christian
We resolve the space complexity of one-pass streaming algorithms for Minimum Dominating Set (MDS) in both insertion-only and insertion-deletion streams (up to poly-logarithmic factors) where an input graph is revealed by a sequence of edge updates. R
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6a26ceb2a642a3cf4ef2ef35b25155c9
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et al. [STOC'07], has played an important role in lower bounds for graph problems in the streaming model (e.g., subgraph counting, maximum matching, MAX-CUT, Schatte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b60611bdf694cfc35bfdd14a46e6e7a0
http://arxiv.org/abs/2107.02578
http://arxiv.org/abs/2107.02578
In this paper, we study edit distance (ED) and longest common subsequence (LCS) in the asymmetric streaming model, introduced by Saks and Seshadhri [Saks and Seshadhri, 2013]. As an intermediate model between the random access model and the streaming
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3a296175666ea7523f53c51cb9f5aaa7
The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are k players with subsets S¹, …, S^k, each drawn from {1, 2, …, n}, and we are promised that e
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::12cbbbb8f29055d54a494c4b32095298
Autor:
Le Gall, Fran��ois, Miyamoto, Masayuki
The distributed subgraph detection asks, for a fixed graph H, whether the n-node input graph contains H as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d789dc195e358b0bb96c1839fa6de825
Autor:
Assadi, Sepehr, Dudeja, Aditi
The goal of this paper is to understand the complexity of a key symmetry breaking problem, namely the (α,β)-ruling set problem in the graph streaming model. Given a graph G = (V,E), an (α, β)-ruling set is a subset I ⊆ V such that the distance
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7b11b7f9ca739201445389578db3a620