Anzeige
Erschienen in:
19.06.2023
Foreword: a Commemorative Issue for Alan L. Selman
Erschienen in: Theory of Computing Systems | Ausgabe 3/2023
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Excerpt
Alan L. Selman (1941 - 2021) was a former Editor-in-Chief of the journal Theory of Computing Systems. To commemorate his extraordinary contributions to theoretical computer science, we solicited papers from the theory community. Nine groups responded to the call, which we present in this issue.-
In “Holographic algorithms on domains of general size,” a Zhiguo Fu and Jin-Yi Cai study the Simultaneously Realizability Problem in holographic algorithm construction. The authors construct a polynomial-time algorithm for the problem on domain size \(k\ge 3\) where the signatures are realizable by “matchgates” over a basis of size 1.
-
In “Subclasses of Ptime interpreted by programming languages,” Siddharth Bhaskar, Cynthia Kop, and Jakob Grue Simonsen study the cons-free programming language of Neil Jones (who collaborated with Alan and, sadly, left this universe in April this year). They study the relationship between polynomial-step cons-free programs, polynomial-size circuits, and polynomial time-bounded Turing machines. They show that for each polynomial p, a polynomial-time decidable relation R exists that forces cons-free programs to spend polynomial time almost everywhere.
-
The paper “Dimension and the structure of complexity classes,” by Jack Lutz, Neil Lutz, and Elvira Mayordomo investigates the Point-to-Set Principle in complexity-theoretic dimension theory, which connects the Hausdorff and the algorithm dimension of real numbers. A key result in the paper includes that if \(\textrm{NP}\) has a positive dimension in \(\textrm{EXP}\) then no quasi-polynomial-time selective language is \(\textrm{NP}\)-hard under \(\le ^p_m\)-reductions.
-
In “Ergodic theorems and converses for \(\textrm{PSPACE}\) functions,” Satyadev Nandakumar and Subin Pulari initiate the study of ergodic theorems in resource-bounded measure theory. While ergodic theorems do not always have a reasonable convergence speed, the authors show they do in their proposed setting. A primary result of the paper is that for \(\textrm{PSPACE}\) \(L^1\) functions on Bernoulli systems, the ergodic average exists. They also show that the \(\textrm{PSPACE}\) non-random numbers are the points where the \(\textrm{PSPACE}\) ergodic theorems do not hold.
-
The paper “The complexity of grid coloring” by Daniel Apon, William Gasarch, and Kevin Lawler studies the c-coloring problem of a partially colored rectangular grid. Here the coloring condition is that for no combinations of four points on the grid that form a rectangle, the colors of the four points should not be monochromatic. The authors show that the problem is \(\textrm{NP}\)-complete. They also provide a Fixed Parameter Tractable algorithm with c as the parameter.
-
In “Effective guessing has unlikely consequences,” Andrá Z. Salamon and Michael Wehar explore the question of whether effective guessing strategies exist for speeding up deterministic computation. They show that the existence of such strategies would result in unexpected consequences like \(\textrm{P} \subset \textrm{DTIME}(n)\). They also show that a logarithmic speed-up using nondeterministic guesses would result in \(\textrm{SAT} \in \textrm{NTIME}(n)\).
-
In “Synchronous Boolean finite dynamical systems on directed graphs over XOR functions,” Mitsunori Ogihara and Kei Uchizawa study the synchronous Boolean finite dynamical systems that operate synchronously with the XOR function as the computing basis and provide complexity-theoretic characterizations of problems about the structure of their configuration graphs.
-
In “Arithmetic circuits, structured matrices and (not so) deep learning,” Atri Rudra surveys the results at the intersection of arithmetic circuit complexity, structured matrices, and deep learning. The motivation for work is to use structured matrices for weight matrices in deep-learning architectures and understand how complexity theory can help shape research in deep learning.
-
The paper “Polynomial-time axioms of choice and polynomial-time cardinality” by Joshua Grochow studies the Axiom of Choice in complexity theory. Some statements of the axiom are known to be equivalent in ZF but inequivalent from a different perspective. The author shows that surprisingly, many versions of the axiom in the polynomial-time setting are equivalent. The author also develops a theory of polynomial-time cardinality, extending the scope of existing works.