Theory and Applications of Models of Computation

Ding-Zhu Du, Donglei Du, Chenchen Wu, Dachuan XuLecture Notes in Computer Science 2022 · DOI · OpenAlex

This document represents the proceedings of the 17th Annual Conference on Theory and Applications of Models of Computation (TAMC 2022), held in Tianjin, China. Rather than a single study, it is a curated collection of 33 research papers that define the current frontier of theoretical computer science, ranging from abstract computability to the mathematical foundations of artificial intelligence.

TL;DR

The TAMC 2022 proceedings highlight a significant shift in theoretical computer science toward bridging the gap between classical complexity theory and modern machine learning. Key contributions focus on advancing submodular optimization, refining approximation algorithms for NP-hard problems, and expanding the utility of zero-knowledge proofs in non-traditional contexts.

What Problem Does This Paper Address?

The core challenge addressed by this collection is the ongoing need to develop more efficient and robust models of computation. As real-world problems in AI, network science, and logistics grow in complexity, standard algorithmic approaches often hit "complexity walls."

The researchers in this volume tackle several specific gaps:

  1. Optimization under Constraints: Many real-world problems (like sensor placement or viral marketing) rely on submodular functions. The papers here seek better approximation ratios when these functions are subject to complex constraints like matroids or knapsacks.
  2. Algorithmic Efficiency: Finding "almost linear time" solutions for graph problems (like isomorphism) or better approximation algorithms for the Traveling Salesman Problem (TSP).
  3. Privacy and Verification: Developing Zero-Knowledge Proofs (ZKP) that are not just mathematically sound but can be applied to physical games and logic puzzles, ensuring privacy without requiring massive computational overhead.

Methods

Because this is a conference proceedings, the methods are diverse but generally fall into three categories:

  • Approximation Algorithms: Many authors propose new "greedy" or iterative algorithms to find near-optimal solutions for NP-hard problems, such as the 3/4 differential approximation for TSP or new bounds for submodular maximization.
  • Complexity Analysis: Several papers utilize parameterized complexity and "almost linear time" analysis to prove that certain problems are more tractable than previously thought under specific conditions (e.g., circle graph isomorphism).
  • Combinatorial Optimization: Techniques involving matroid theory, stochastic variants of the Alternating Direction Method of Multipliers (ADMM), and set-theoretic representations are used to solve high-dimensional optimization problems.

Datasets

As a primarily theoretical volume, most papers do not rely on large-scale empirical datasets. Instead, they use:

  • Standard Combinatorial Benchmarks: Classic graph structures (planar bipartite graphs, chordal graphs) and matroid constraints.
  • Synthetic Simulations: Used to test the performance of new scheduling or inventory optimization algorithms.
  • Logic Puzzles: Games like Makaro and Usowan serve as "datasets" for testing new physical Zero-Knowledge Proof protocols.

Key Insights and Ideas

  • The Rise of Submodularity: A large portion of the research focuses on "k-submodular" and "DR-submodular" functions. The "aha moment" here is the realization that these mathematical properties are the key to making machine learning models more interpretable and efficient.
  • Physical ZKP: One of the more creative insights is the application of cryptography to physical objects. Researchers demonstrated how a standard deck of cards can be used to provide a zero-knowledge proof for logic puzzles, suggesting that high-level privacy concepts can be implemented with low-tech tools.
  • Refining Graph Theory: The proceedings suggest that the "low-hanging fruit" in graph theory has been picked; current research is now diving deep into very specific graph classes (like "Planar Bipartite" or "Dual-Attribute Networks") to find specialized efficiencies that general algorithms miss.

Key Results

  • Acceptance Standards: The conference maintained a rigorous selection process, accepting only 33 papers out of 75 submissions (a 44% acceptance rate), ensuring high-quality theoretical contributions.
  • Algorithmic Breakthroughs: Notable results include a new 3/4 differential approximation for the Traveling Salesman Problem and "almost linear time" algorithms for circle graph isomorphism.
  • Optimization Bounds: Several papers established new, tighter approximation ratios for submodular maximization under matroid and knapsack constraints, which are critical for resource allocation in cloud computing and network design.

Limitations and Future Work

The primary limitation acknowledged across these papers is the gap between theory and practice. While many algorithms are proven to be "efficient" in a big-O sense, their constant factors or the specific constraints required (e.g., "equal-length jobs" in scheduling) may limit their immediate application in messy, real-world environments.

Future work suggested by the editors and authors includes:

  • Extending these theoretical models to Foundations of Artificial Intelligence, specifically looking at how submodular optimization can improve deep learning training.
  • Moving from offline to online optimization, where data arrives in a stream and decisions must be made without knowing the future (as seen in the paper on "Online Weakly DR-Submodular Optimization").

Summary updated

BibTeX
@inproceedings{du2022theory,
  author = {Ding-Zhu Du and Donglei Du and Chenchen Wu and Dachuan Xu},
  title = {{Theory and Applications of Models of Computation}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2022},
  doi = {10.1007/978-3-031-20350-3},
}

Loading related content...

Figure