495 research outputs found
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal
No full textThe Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time O(n^{tw(H)+1}) [Alon, Yuster, Zwick'95], where n is the number of vertices of the host graph G. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of O(n^{tw(H)+1-ε}) or even faster (e.g. for k-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time n^{o(tw(H) / log(tw(H)))} for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07].
In this paper, we demonstrate the existence of maximally hard pattern graphs H that require time n^{tw(H)+1-o(1)}. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth t:
For any ε > 0 there exists t ≥ 3 and a pattern graph H of treewidth t such that Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}).
Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth t ≥ 3:
For any t ≥ 3 there exists a pattern graph H of treewidth t such that for any ε > 0 Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}).
In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for tw < 3, (3) Subgraph Isomorphism parameterized by pathwidth instead of treewidth, and (4) a weighted variant that we call Exact Weight Subgraph Isomorphism, for which we examine pseudo-polynomial time algorithms. For many of these settings we obtain similarly tight upper and lower bounds
Dark matter from late decays and the small-scale structure problems
No full textThe generation of dark matter in late decays of quasi-stable massive particles has been proposed as a viable framework to address the excess of power found in numerical N-body simulations for cold dark matter cosmologies. We identify a convenient set of variables to illustrate which requirements need to be satisfied in any generic particle physics model to address the small scale problems and to fulfill other astrophysical constraints. As a result of this model-independent analysis, we point out that meeting these requirements in a completely natural way is inherently difficult. In particular, we re-examine the role of gravitinos and Kaluza-Klein gravitons in this context and find them disfavoured as a solution to the small-scale problems in case they are DM candidates generated in the decay of thermally produced WIMPs. We propose right-handed sneutrinos and right-handed Kaluza-Klein neutrinos as alternatives. We find that they are viable dark matter candidates, but that they can contribute to a solution of the small scale problems only in case the associated Dirac neutrino mass term appears as a subdominant contribution in the neutrino mass matrix
Efficient optimization of many objectives by approximation-guided evolution
No full textAbstract not availableMarkus Wagner, Karl Bringmann, Tobias Friedrich, Frank Neuman
Approximation-guided evolutionary multi-objective optimization
No full textMulti-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multi-objective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms state-of-the-art evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.Karl Bringmann, Tobias Friedrich, Frank Neumann, Markus Wagne
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
No full textWe present a pseudopolynomial-time algorithm for the Knapsack problem that has running time Õ(n + t√{p_{max}}), where n is the number of items, t is the knapsack capacity, and p_{max} is the maximum item profit. This improves over the Õ(n + t p_{max})-time algorithm based on the convolution and prediction technique by Bateni et al. (STOC 2018). Moreover, we give some evidence, based on a strengthening of the Min-Plus Convolution Hypothesis, that our running time might be optimal.
Our algorithm uses two new technical tools, which might be of independent interest. First, we generalize the Õ(n^{1.5})-time algorithm for bounded monotone min-plus convolution by Chi et al. (STOC 2022) to the rectangular case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to balanced instances, where all items have nearly the same profit-to-weight ratio, up to a constant factor.
Using these techniques, we can also obtain algorithms that run in time Õ(n + OPT√{w_{max}}), Õ(n + (nw_{max}p_{max})^{1/3}t^{2/3}), and Õ(n + (nw_{max}p_{max})^{1/3} OPT^{2/3}), where OPT is the optimal total profit and w_{max} is the maximum item weight
Ramanujan's mock theta functions and their applications (after Zwegers and Ono-Bringmann)
No full textThis is an important expository paper based on recent work of \\it K. Bringmann and \\it K. Ono [Ann. Math. (2) 171, No. 1, 419--449 (2010; Zbl 05712731)] and \\it S. P. Zwegers [Contemp. Math. 291, 269--277 (2001; Zbl 1044.11029), ``Mock theta functions.'' Utrecht: Universiteit Utrecht, Faculteit Wiskunde en Informatica (Thesis) (2002; Zbl 1194.11058), Ramanujan J. 20, No. 2, 207--214 (2009; Zbl 1207.11053), and Bull. Lond. Math. Soc. 42, No. 2, 301--311 (2010; Zbl 1198.11047)] on Ramanujan's mock theta functions. These are certain q-series which belong to at least one (and presumably to all) of the following three families of functions: Appell-Lerch sums, quotients of indefinite binary theta series by unary theta series, and Fourier coefficients of meromorphic Jacobi forms. After giving some background, the author briefly reviews Zwegers' study of the transformation properties of these three families of functions and his construction of non-holomorphic correction terms used to make these functions modular. Motivated by Zwegers' work, the author then introduces the notion of a mock modular form and its shadow, discusses the relation between mock modular forms and the harmonic weak Maass forms of Bruinier and Funke, and collects a number of new examples. Finally, the author touches on some of Bringmann and Ono's applications of these ideas to the study of ranks of partitions
Entre os índios do Sul: uma análise da atuação indigenista do SPI e de suas propostas de desenvolvimento educacional e agropecuário nos postos indígenas Nonoai/RS e Xapecó/SC (1941-1967)
No full textTese (doutorado) - Universidade Federal de Santa Catarina, Centro de Filosofia e Ciências Humanas, Programa de Pós-Graduação em História, Florianópolis, 2015.Esta tese tem como objetivo suscitar reflexões sobre atuação tutelar do SPI entre os Kaingang na região Sul do Brasil, analisando as peculiaridades referentes aos contextos dos Postos Indígenas Nonoai (RS) e Xapecó (SC), entre os anos de 1941 e 1967. Por meio de pesquisa documental e bibliográfica, apresento informações sobre os primórdios da atuação tutelar nas duas áreas indígenas, ressaltando os principais obstáculos para a execução das políticas indigenistas nos primeiros anos do SPI nestes estabelecimentos. Destaco a conjuntura histórica que proporcionou a criação e a sistematização das modalidades educacionais e de trabalho agropecuário nos padrões do desenvolvimentismo rural presente entre as décadas de 1940 e 1960. Do mesmo modo, ressalto a representatividade deste órgão e de sua atuação entre os Kaingang dos dois PIs, buscando destacar de que maneira os indígenas se envolveram ou foram envolvidos nas estratégias de desenvolvimento agropecuário e educacional promovidas pelo SPI. Neste sentido, contribuem para as reflexões aqui propostas, os depoimentos orais de velhos Kaingang que vivenciaram este processo. Através de seus relatos, de suas percepções e de seus posicionamentos, busco avaliar a participação dos indígenas nas propostas do SPI. Em suma, com este estudo, pretendo explicar quais foram os principais efeitos das políticas indigenistas de caráter desenvolvimentista e de que forma as concepções particulares dos indígenas, dos funcionários do SPI e da própria sociedade regional envolvente, influenciaram no desenvolvimento de tais ações entre os Kaingang dos Postos Indígenas Nonoai e Xapecó.Abstract : This thesis aims to raise reflections about the tutelary role of the Indian Protection Service (Serviço de Proteção aos Índios - SPI) among the Kaingang in South Brazil, analyzing the peculiarities related to the contexts of Indian Posts Nonoai (RS) and Xapecó (SC), between the years 1941 and 1967. Through documental and bibliographical research, I present information about the origins of the tutelary role in two indigenous areas, emphasizing the main obstacles to the implementation of indigenous policies in the early years of the SPI at these establishments. I highlight the historical circumstances that led to the creation and the systematization of the educational genres and agricultural work in the patterns of the rural developmentalism present between the 1940s and 1960s. Similarly, detach the representativeness of this institution and its actions between the Kaingang on both PIs, with special emphasis on how the Indians got involved or were involved on the agricultural and educational strategies of development promoted by the SPI. In this sense, they contribute to the reflections proposed here, the oral testimony of Kaingang elderly who experienced this process. Through their stories, their perceptions and their positions, I seek to evaluate the indigenous participation on the SPI proposals. In short, with this study, I intend to explain what were the main effects of indigenous policies of developmental character and how the particular conceptions from indigenous, from the SPI officials and from the people of the surrounded society, had influenced on the development of such actions among Kaingang of the Indian Posts Nonoai and Xapecó
Balls into bins via local search: cover time and maximum load
No full textWe study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case m=n, we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest m so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when m>=n
sj-docx-1-psp-10.1177_01461672231211469 – Supplemental material for Studying Daily Social Interaction Quantity and Quality in Relation to Depression Change: A Multi-Phase Experience Sampling Study
No full textSupplemental material, sj-docx-1-psp-10.1177_01461672231211469 for Studying Daily Social Interaction Quantity and Quality in Relation to Depression Change: A Multi-Phase Experience Sampling Study by Timon Elmer, Nilam Ram, Andrew T. Gloster and Laura F. Bringmann in Personality and Social Psychology Bulletin</p
- …
