Temat: 3-sum - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Deterministic 3SUM-Hardness
Autorzy:: Fischer, Nick
Polak, Adam
Kaliciak, Piotr
Opis:: As one of the three main pillars of fine-grained complexity theory, the 3SUM problem explains the hardness of many diverse polynomial-time problems via fine-grained reductions. Many of these reductions are either directly based on or heavily inspired by Pătraşcu’s framework involving additive hashing and are thus randomized. Some selected reductions were derandomized in previous work [Chan, He; SOSA'20], but the current techniques are limited and a major fraction of the reductions remains randomized. In this work we gather a toolkit aimed to derandomize reductions based on additive hashing. Using this toolkit, we manage to derandomize almost all known 3SUM-hardness reductions. As technical highlights we derandomize the hardness reductions to (offline) Set Disjointness, (offline) Set Intersection and Triangle Listing - these questions were explicitly left open in previous work [Kopelowitz, Pettie, Porat; SODA'16]. The few exceptions to our work fall into a special category of recent reductions based on structure-versus-randomness dichotomies. We expect that our toolkit can be readily applied to derandomize future reductions as well. As a conceptual innovation, our work thereby promotes the theory of deterministic 3SUM-hardness. As our second contribution, we prove that there is a deterministic universe reduction for 3SUM. Specifically, using additive hashing it is a standard trick to assume that the numbers in 3SUM have size at most n³. We prove that this assumption is similarly valid for deterministic algorithms.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 2.

Tytuł:: Nowe podejścia do rozwiązania problemu 3SUM
On recent attempts to solve the 3SUM problem
Autorzy:: Borak, Helena
Opis:: The 3SUM problem is well known problem in computer science. In this paper we focus on presenting the approaches applied recently to solve this problem in subquadratic time. The main part is devoted to precise consideration of research by Chan and Lewenstein allowing deeper understanding of algebraic theories and ideas behind it. In the second part of paper we show other related problems and approaches worth considering.
Problem 3SUM jest dobrze znany w informatyce. W niniejszej pracy są prezentowane nowe podejścia do rozwiązania tego problemu w czasie podkwadratowym. Część główna jest poświęcona dokładnej analizie pracy Chana i Lewensteina, pozwalając na głębsze zrozumienie algebraicznych twierdzeń i koncepcji stanowiące jej podstawę. W drugiej części pracy zostały pokazane inne powiązane problemy i podejścia warte rozważenia.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 3.

Tytuł:: Monochromatic triangles, intermediate matrix products, and convolutions
Autorzy:: Lincoln, Andrea
Polak, Adam
Vassilevska Williams, Virginia
Wydawca:: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Opis:: The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(n^ω) time algorithms for ω < 2.373. On the other hand, the (min,+) matrix product which is at the heart of many fundamental graph problems such as All-Pairs Shortest Paths, has received only minor n^o(1) improvements over its brute-force cubic running time and is widely conjectured to require n^{3-o(1)} time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems. For instance, the Min-Max matrix product, the Minimum Witness matrix product, All-Pairs Shortest Paths in directed unweighted graphs and determining whether an edge-colored graph contains a monochromatic triangle, can all be solved in Õ(n^{(3+ω)/2}) time. While slight improvements are sometimes possible using rectangular matrix multiplication, if ω=2, the best runtimes for these "intermediate" problems are all Õ(n^2.5). A similar phenomenon occurs for convolution problems. Here, using the FFT, the usual (+,×)-convolution of two n-length sequences can be solved in O(n log n) time, while the (min,+) convolution is conjectured to require n^{2-o(1)} time, the brute force running time for convolution problems. There are analogous intermediate problems that can be solved in O(n^1.5) time, but seemingly not much faster: Min-Max convolution, Minimum Witness convolution, etc. Can one improve upon the running times for these intermediate problems, in either the matrix product or the convolution world? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way? This paper makes progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and Minimum Witness product can be reduced to both the Min-Max product and a variant of the monochromatic triangle problem, so that a significant improvement over n^{(3+ω)/2} time for any of the latter problems would result in a similar improvement for both of the former problems. We also show that a natural convolution variant of monochromatic triangle is fine-grained equivalent to the famous 3SUM problem. As this variant is solvable in O(n^1.5) time and 3SUM is in O(n^2) time (and is conjectured to require n^{2-o(1)} time), our result gives the first fine-grained equivalence between natural problems of different running times. We also relate 3SUM to monochromatic triangle, and a coin change problem to monochromatic convolution, and thus to 3SUM.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 4.

Tytuł:: Beta invariant and chromatic uniqueness of wheels
Autorzy:: Lee, Sooyeon
Wu, Haidong
Tematy:: chromatic uniqueness of graphs
beta invariant
characteristic polynomial
2-sum
3-sum
matroids; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59882201.pdf Link otwiera się w nowym oknie
Opis:: A graph $G$ is chromatically unique if its chromatic polynomial completely determines the graph. An $n$-spoked wheel, $W_n$, is shown to be chromatically unique when $n\ge 4$ is even [S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207–212]. When $n$ is odd, this problem is still open for $n\ge 15$ since 1984, although it was shown by different researchers that the answer is no for $n=5, 7$, yes for $n=3, 9, 11, 13$, and unknown for other odd $n$. We use the beta invariant of matroids to prove that if $M$ is a 3-connected matroid such that $|E(M)| = |E(W_n)|$ and $\beta(M) = \beta(M(W_n))$, where $\beta(M)$ is the beta invariant of $M$, then $M \cong M(W_n)$. As a consequence, if $G$ is a 3-connected graph such that the chromatic (or flow) polynomial of $G$ equals to the chromatic (or flow) polynomial of a wheel, then $G$ is isomorphic to the wheel. The examples for $n=3, 5$ show that the 3-connectedness condition may not be dropped. We also give a splitting formula for computing the beta invariants of general parallel connection of two matroids as well as the 3-sum of two binary matroids. This generalizes the corresponding result of Brylawski [A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1–22].
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Przegląd rezultatów związanych z trudnością problemów wielomianowych
A survey of hardness results in P.
Autorzy:: Pitrus, Bruno
Opis:: The aim of this work is to introduce the reader to the theory of fine-grained complexity. We present the main hypotheses of this new field of computational complexity and some conditional hardness proofs. We reduce the orthogonal vectors problem to some dynamic problems on strings; the 3SUM problem to some computational geometry problems; and we present many equivalent formulations of the all-pairs shortest paths conjecture.
Celem tej pracy jest wprowadzenie czytelnika w teorię złożoności drobnoziarnistej. Przedstawiamy główne hipotezy tego nowego działu złożoności obliczeniowej i kilka warunkowych dowodów trudności. Redukujemy problem wektorów prostopadłych do tekstowych problemów programowania dynamicznego; problem 3SUM do kilku problemów geometrii obliczeniowej; przedstawiamy wiele równoważnych sformułowań hipotezy o najkrótszych ścieżkach.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 6.

Tytuł:: Equivalences between triangle and range query problems.
Równoważności pomiędzy zliczaniem trójkątów a problemami na przedziałach
Autorzy:: Kleiner, Krzysztof
Opis:: Dowodzimy redukcji pomiędzy problemami na przedziałach a problemami dotyczącym zliczania i wypisywania trójkątów w grafach. Wskazujemy ogólne warunki, jakie musi spełniać problem na przedziałach, aby należeć do wprowadzonej przez nas klasy. Pokazujemy, że wszystkie takie problemy są równoważne (z dokładnością do czynników polilogarytmicznych) do siebie wzajemnie oraz do problemu zliczania trójkątów przechodzących przez dane krawędzie grafu.Analizujemy zależności pomiędzy problemami dotyczącymi trójkątów. Wskazujemy redukcje pomiędzy wypisywaniem trójkątów a wariantami problemów dotyczących ich znajdowania i zliczania, tworząc drugą klasę równoważnych sobie problemów. Jako uboczny efekt tych redukcji, otrzymujemy również nowy algorytm wypisywania trójkątów o takiej samej złożoności jak najlepszy znany algorytm rozwiązujący ten problem.Otrzymane równoważności pociągają ograniczenia górne $\Oh{n^{2\omega/(\omega+1)}}\leq\Oh{n^{1.41}}$ oraz warunkowe (oparte o Hipotezę 3SUM) ograniczenia dolne $\Omega{n^{4/3}}$ dla złożoności czasowej problemów z naszej klasy z dokładnością do czynników polilogarytmicznych. Te wartości zrównały by się, gdyby zachodziło $\omega=2$, w którym to przypadku złożoność tych problemów była by ostatecznie rozstrzygnięta. Pokazujemy nowy algorytm rozwiązywania problemów na przedziałach, który uogólnia powyższy czas działania na problemy online oraz na instancje których złożoność zdefiniowana jest za pomocą dwóch parametrów, osiągając na wszystkich klasach wejść lepszą złożoność czasową niż obecnie znane algorytmy.
We establish a set of fine-grained reductions between range query problems and the problems of counting and listing triangles in graphs. We show general conditions for range query problems to belong to our complexity class and prove that all such problems are equivalent\n (up to polylogarithmic factors) to each other and to the~problem of~per-edge counting of~triangles in graphs.We further analyse the relationships within the family of triangle problems, showing reductions between the triangle listing and per-edge triangle detection and counting, establishing a~second class of equivalent problems. As a byproduct, our proofs also produce an alternative simple triangle listing algorithm matching the complexity of the state-of-the-art solution.The obtained equivalences demonstrate, up to polylogarithmic factors, the upper bounds of $\Oh{n^{2\omega/(\omega+1)}}\leq\Oh{n^{1.41}}$ and~the conditional 3SUM-based lower bounds of $\Omega{n^{4/3}}$ for the problems in our class. Those~two figures would match if $\omega=2$, in which case the complexity of the range query problems would be settled. We create an algorithm matching this running time and extending it to online problems as well as to problems defined in terms of two parameters, improving upon the running time of existing algorithms for all classes of inputs.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 7.

Tytuł:: Measurement of the doubly-polarized $^{3}\vec{H}e(\vec{\gamma},n)pp$ reaction at 16.5 MeV and its implications for the GDH sum rule
Autorzy:: Ahmed, M. W.
Skibiński, Roman
Laskaris, G.
Zimmerman, W. R.
Deltuva, A.
Sauer, P. U.
Flower, C.
Heideman, J. N.
Meziane, M.
Fonseca, A. C.
Xiong, W.
Witała, Henryk
Karwowski, H. J.
Wu, Y. K.
Gao, H.
Weller, H. R.
Golak, Jacek
Averett, T.
Chu, P.-H.
Mueller, J. M.
Strakovsky, I. I.
Yan, X.
Opis:: We report new measurements of the double-polarized photodisintegration of 3He at an incident photon energy of 16.5 MeV, carried out at the High Intensity γ-ray Source (HIγS) facility located at Triangle Universities Nuclear Laboratory (TUNL). The spin-dependent double-differential cross sections and the contribution from the three-body channel to the Gerasimov–Drell–Hearn (GDH) integrand were extracted and compared with the state-of-the-art three-body calculations. The calculations, which include the Coulomb interaction and are in good agreement with the results of previous measurements at 12.8 and 14.7 MeV, deviate from the new cross section results at 16.5 MeV. The GDH integrand was found to be about one standard deviation larger than the maximum value predicted by the theories.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Twierdzenie Knesera dla 3-rozmaitości
Kneser theorem for 3-manifolds
Autorzy:: Dudek, Maria
Opis:: In this paper I present Hellmuth Kneser decomposition theorem from 1928, which was historically the first reduction of the classification problem for 3-dimensional manifolds. The theorem states that every compact 3-manifold can be decomposed uniquely into a connected sum of nontrivial and prime summands. The first and second chapter of this work is to establish fundamental tools (of general and algebraic, subsequently pl topology) that are needed for the proofs of existence and uniqueness of prime decomposition. The third and main chapter is to define connected sum of 3-manifolds and prove the Kneser theorem.
Praca prezentuje pierwszy historycznie krok na drodze do klasyfikacji rozmaitości wymiaru 3, jakim było twierdzenie o rozkładzie niemieckiego matematyka Hellmutha Knesera z 1928 roku. Twierdzenie to orzeka, iż każdą zwartą 3-rozmaitość można przedstawić jednoznacznie (przy odpowiednim doprecyzowaniu tej jednoznaczności) w postaci sumy spójnej nietrywialnych i pierwszych (ze względu na tę operację) 3-rozmaitości. Pierwszy i drugi rozdział pracy służy wprowadzeniu narzędzi (najpierw z zakresu topologii ogólnej i algebraicznej, a następnie topologi kawałkami liniowej), niezbędnych do przeprowadzenia dowodów istnienia i jednoznaczności rozkładu. Trzeci rozdział to właściwa część pracy, czyli wprowadzenie pojęcia sumy spójnej i dowód twierdzenia Knesera.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 9.

Tytuł:: On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
Autorzy:: Bensmail, Julien
Inerney, Fionn Mc
Lyngsie, Kasper Szabo
Tematy:: neighbour-sum-distinguishing edge-weightings
bipartite graphs
odd weights
1-2-3 Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32361745.pdf Link otwiera się w nowym oknie
Opis:: For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑_e∈E(v) w(e) ≠ ∑_e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a+2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a+2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a+2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: An Oriented Version of the 1-2-3 Conjecture
Autorzy:: Baudon, Olivier
Bensmail, Julien
Sopena, Éric
Tematy:: oriented graph
neighbour-sum-distinguishing arc-weighting
complexity
1-2-3 Conjecture; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339138.pdf Link otwiera się w nowym oknie
Opis:: The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph $G$ with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of $G$. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph $\overrightarrow{G}$ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of $\overrightarrow{G}$ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an $\mathsf{NP}$-complete problem. These results also hold for product or list versions of this problem.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "3-sum" wg kryterium: Temat