Theory Track

Prove Something Nobody Knows

For Mathematicians, Theoretical Computer Scientists, and Anyone Who Loves Proofs

You don’t want to build things. You want to understand things.

What are the convergence guarantees? What’s the complexity class? Why do power laws emerge?

This track is for you.

The Open Problems

1. STAN Convergence

The Formula:

effective_cost(e) = base_weight(e) / (1 + pheromone(e) × sensitivity)

The Question: Does STAN converge to a stationary pheromone distribution? Under what conditions? How fast?

What’s Known:

• Classical ACO has convergence proofs for specific variants
• STAN differs in cost formula and agent heterogeneity
• Empirical evidence suggests convergence, but no proof

The Prize: First rigorous convergence proof gets $1,000 bonus + publication opportunity

2. Complexity Classification

The Decision Problem:

Given graph G, pheromone dynamics D, and threshold k, does there exist a stationary configuration where minimum path cost ≤ k?

The Question: What complexity class?

Possibilities:

• In P for restricted graph classes?
• NP-complete in general?
• PSPACE-complete?
• Something else?

The Prize: Definitive classification gets $2,000 bonus

3. Power-Law Emergence

The Observation: 0.4% of edges carry 94.9% of pheromone. Distribution follows P(p) ∝ p^(-γ).

The Question: Why? What mathematical structure guarantees this?

Intuition: Rich-get-richer dynamics (preferential attachment). But formal proof?

The Prize: Derive the exponent analytically for $500 bonus

4. Optimality Bounds

The Question: How close to optimal does STAN get?

Formalize: Let OPT be the true minimum path cost. Let STAN(t) be the expected cost under pheromone distribution at time t.

Prove: STAN(t) ≤ f(t) × OPT for some function f.

Connection: Approximation algorithms, competitive analysis.

5. Agent Heterogeneity

The Setup: Different agents have different sensitivity α ∈ [0, 1].

The Question: What distribution of α optimizes colony performance?

Connection: Portfolio theory, exploration-exploitation tradeoff.

What You’ll Need

Mathematical Background

• Graph theory (paths, connectivity, weights)
• Probability (Markov chains, stationary distributions)
• Analysis (fixed points, convergence)
• Complexity theory (reductions, completeness)

From Us

• Precise algorithm specification
• Empirical data to inform conjectures
• CS collaborators for implementation
• Physics collaborators for intuition

Deliverables

Your submission should include:

1. Statement — Precise theorem or conjecture
2. Proof/Evidence — Complete proof or partial progress with clear gaps
3. Implications — What does this tell us about stigmergic systems?
4. Open Questions — What remains unknown?

Judging Criteria

Past Work to Build On

• Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey.
• Stutzle, T., & Dorigo, M. (2002). A short convergence proof for a class of ACO algorithms.
• Gutjahr, W. J. (2002). ACO algorithms with guaranteed convergence to the optimal solution.

Note: STAN differs from classical ACO. These proofs may not directly apply.

Team Composition

Required:

• At least one mathematician or theoretical CS researcher
• At least one person from another discipline

Recommended:

• Complexity theorist (for hardness results)
• Probabilist (for stochastic analysis)
• Physicist (for intuition about dynamics)

Timeline

Mentors

• Robin Dey — STAN algorithm author, can clarify algorithm details
• [Math Faculty] — Can advise on proof techniques
• [Physics Faculty] — Can provide intuition about dynamics

“A proof is a proof. What kind of proof? A proof is a proof, and when you have a good proof, it’s because it’s proven.”

— Jean Chrétien (on a very different topic)

You’ve proven theorems about graphs, algorithms, and stochastic processes.

Now prove theorems about emergence.

[REGISTER FOR THEORY TRACK]