There is a vast theory of the asymptotic behavior of orthogonal polynomials with respect to a measure on R \mathbb {R} and its applications to Jacobi matrices. That theory has an obvious affine invariance and a very special role for ∞ \infty . We extend aspects of this theory in the setting of rational functions with poles on R ¯ = R ∪ { ∞ } \overline {\mathbb {R}} = \mathbb {R} \cup \{\infty \} , obtaining a formulation which allows multiple poles and proving an invariance with respect to R ¯ \overline {\mathbb {R}} -preserving Möbius transformations. We obtain a characterization of Stahl–Totik regularity of a GMP matrix in terms of its matrix elements; as an application, we give a proof of a conjecture of Simon – a Cesàro–Nevai property of regular Jacobi matrices on finite gap sets.
more »
« less
GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
Graph Isomorphism (GI) is one of a small number of natural algorithmic problems with unsettled complexity status in the P / NP theory: not expected to be NP-complete, yet not known to be solvable in polynomial time.
Arguably, the GI problem boils down to filling the gap between symmetry and regularity, the former being defined in terms of automorphisms, the latter in terms of equations satisfied by numerical parameters.
Recent progress on the complexity of GI relies on a combination of the asymptotic theory of permutation groups and asymptotic properties of highly regular combinatorial structures called coherent configurations. Group theory provides the tools to infer either global symmetry or global irregularity from local information, eliminating the symmetry/regularity gap in the relevant scenario; the resulting global structure is the subject of combinatorial analysis. These structural studies are melded in a divide-and-conquer algorithmic framework pioneered in the GI context by Eugene M. Luks (1980).
more »
« less
- Award ID(s):
- 1718902
- PAR ID:
- 10179670
- Date Published:
- Journal Name:
- Proceedings of the International Congress of Mathematicians, ICM 2018
- Volume:
- 3
- Page Range / eLocation ID:
- 3319 to 3336
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Objective Individuals with a gastrointestinal (GI) disorder often alter their diet to manage GI symptoms, adding complexity to understanding the diverse motivations contributing to food avoidance/restriction. When a GI disorder is present, the DSM‐5 states that Avoidant/Restrictive Food Intake Disorder (ARFID) can be diagnosed only when eating disturbance exceeds that expected. There is limited guidance to make this determination. This study attempts to address this gap by characterizing the presentation of ARFID in adults with and without a self‐reported GI disorder.
Method Participants were 2,610 adults ages 18–44 who self‐identified as “picky eaters.” Participants reported on motivations for food avoidance, affective experiences towards food, and perceived impairment. Responses were compared across four groups: GI issues and likely ARFID (L‐ARFID/GI), L‐ARFID‐only, GI‐only, and No‐ARFID/No‐GI.
Results Groups with a GI disorder (L‐ARFID/GI, GI‐only) reported more fear of aversive consequences of eating than those without a GI disorder, while groups with L‐ARFID (L‐ARFID, L‐ARFID/GI) evidenced significantly greater sensory aversion to food and indifference to food or eating, negative emotional reactions to food and overall disgust sensitivity, and eating related impairment.
Discussion Consideration of the interplay of a GI disorder with ARFID can add precision to case conceptualization. Food avoidance may be attempts to manage fears of aversive consequences that are augmented by a history of GI symptoms, while sensory aversions and negative emotional reactions towards foods may be more elevated in ARFID. These findings emphasize the need to consider an ARFID diagnosis in patients with GI disorders to optimize care.
-
more » « less
Abstract This manuscript presents an algorithmic approach to cooperation in biological systems, drawing on fundamental ideas from statistical mechanics and probability theory. Fisher’s geometric model of adaptation suggests that the evolution of organisms well adapted to multiple constraints comes at a significant complexity cost. By utilizing combinatorial models of fitness, we demonstrate that the probability of adapting to all constraints decreases exponentially with the number of constraints, thereby generalizing Fisher’s result. Our main focus is understanding how cooperation can overcome this adaptivity barrier. Through these combinatorial models, we demonstrate that when an organism needs to adapt to a multitude of environmental variables, division of labor emerges as the only viable evolutionary strategy.
-
Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a bynow classical paper, Beeri, Fagin, Maier, and Yannakakis established several different equivalent characterizations of acyclicity; in particular, they showed that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for relations over that schema holds, which means that every collection of pairwise consistent relations over the schema is globally consistent. Even though real-life databases consist of bags (multisets), there has not been a study of the interplay between local consistency and global consistency for bags. We embark on such a study here and we first show that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for bags over that schema holds. After this, we explore algorithmic aspects of global consistency for bags by analyzing the computational complexity of the global consistency problem for bags: given a collection of bags, are these bags globally consistent? We show that this problem is in NP, even when the schema is part of the input. We then establish the following dichotomy theorem for fixed schemas: if the schema is acyclic, then the global consistency problem for bags is solvable in polynomial time, while if the schema is cyclic, then the global consistency problem for bags is NP-complete. The latter result contrasts sharply with the state of affairs for relations, where, for each fixed schema, the global consistency problem for relations is solvable in polynomial time.more » « less
-
Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parameter tractable results for problems where the number of covariates and the number of levels of each covariate are seen as a parameter.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1142/9789813272880_0183
