Guest Editorial: Computing and Combinatorics

My T. Thai

This article serves as a guest editorial for a special issue of the journal Algorithmica, curated by My T. Thai. The issue synthesizes six selected papers that represent the state-of-the-art research at the intersection of computing and combinatorics as of 2012. These works explore the fundamental boundaries of computational complexity, algorithmic efficiency, and the mathematical properties of combinatorial structures.

Overview of Research Themes

The featured research addresses gaps in three primary domains:

  1. Combinatorial Structures: Developing efficient representations for permutations and cycles.
  2. Computational Complexity: Establishing the hardness of specific problems, such as tile-packing, and defining the boundaries of complexity classes like #NC1.
  3. Algorithmic Optimization: Creating faster exact and approximation algorithms for NP-hard problems, including set cover and maximum biclique identification in specialized graph types.

Methodological Innovations

The papers in this collection utilize a diverse array of methodologies to achieve their results:

  • Cross-Disciplinary Construction: One study draws inspiration from the traditional art of bell-ringing, using "half-hunts" and "cool-lex" ordering to construct universal cycles for permutations. This connects the mathematical "permutohedron" to historical practices to solve modern combinatorial problems.
  • Cryptographic Design: Researchers developed an Equality of Two Discrete Logarithms (EQDL) protocol within the Random Oracle Model (ROM), focusing on leaner zero-knowledge proofs for anonymous credentials.
  • Automata and Complexity Theory: The issue explores the use of visibly pushdown automata to characterize complexity classes, demonstrating that the addition of a "visible stack" to a nondeterministic finite-state automaton captures the distinction between specific classes.
  • Advanced Graph Algorithms: To achieve near-linear time complexity, authors applied the "slowly growing inverse of the Ackermann function" ($\alpha(n)$) to graph-theoretic challenges.

Key Results and Breakthroughs

The editorial highlights several quantitative and theoretical milestones across the featured papers:

Cryptography and Privacy

In the realm of secure communication, a new EQDL protocol was introduced that significantly enhances efficiency. This protocol reduces computational costs by approximately 40% and decreases the prover's message size by roughly 33%, making zero-knowledge proofs more viable for resource-constrained environments.

Graph Theory and Optimization

Significant progress was reported in finding maximum edge bicliques:

  • For convex bipartite graphs, a new algorithm achieves a runtime of $O(n \log^3 n \log \log n)$.
  • For biconvex and bipartite permutation graphs, the complexity was further optimized to $O(n \alpha(n))$ time.

Additionally, the issue presents the first known polynomial-time exact solutions for several variants of the capacitated set cover problem, spanning both geometric and non-geometric contexts.

Complexity and Hardness

Theoretical contributions include a new proof that tile-packing tomography is NP-hard for all types of tiles. This finding establishes a high bar for reconstruction algorithms by proving that the problem's difficulty is universal rather than dependent on specific tile shapes. Furthermore, the issue proves that counting paths in any fixed visibly pushdown automaton is complete for the complexity class #NC1.

Conclusion

The six papers curated for this special issue of Algorithmica demonstrate the vibrant synergy between combinatorial theory and computational application. By providing faster algorithms for graph problems, more efficient cryptographic protocols, and deeper insights into complexity classes, these works continue to define the landscape of modern theoretical computer science.

Summary updated

BibTeX
@article{thai2012guest,
  author = {My T. Thai},
  title = {{Guest Editorial: Computing and Combinatorics}},
  journal = {Algorithmica},
  year = {2012},
  doi = {10.1007/s00453-012-9649-z},
}
Figure