skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: 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
Author(s) / Creator(s):
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
  1. ; ; (, Transactions of the American Mathematical Society, Series B)
    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
  2. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Kráľovič, Rastislav; Kučera, Antonín (Ed.)
    We characterize the algorithmic dimensions (i.e., the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i.e., Martin-Löf random) sequences. Our proof uses Lutz’s and Mayordomo’s respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity. 
    more » « less
  3. ; ; ; (, Scientific Reports)
    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. 
    more » « less
  4. ; (, ACM SIGMOD Record)
    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
  5. ; ; (, Operations Research)
    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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email