/rooted-tree-classifier

See our manuscript at http://arxiv.org/abs/2102.09277

Primary LanguagePythonThe UnlicenseUnlicense

Description

This folder contains a program that decides round complexity of homogenous LCL problems on (binary) trees.

The program uses three subroutines to determines a problem's complexity.

  • constant_decider
    • decides whether a problem is O(1) solvable or it is inherently harder
  • log_decider
    • decides whether a problem is log(n) solvable or it is inherently harder
  • log_star_decider
    • decides whether a problem is log*(n) solvable or it is inherently harder

Usage

  1. Install dependencies by pip3 install -r requirements.txt.

  2. Run python -m rooted_tree_classifier and describe (on standard input) constraints of a problem. For example:

Note that one needs to first run the classifier (python -m rooted_tree_classifier) and only afterwards provide an input on a separate line.

python -m rooted_tree_classifier
111

Expected output is O(1)

python -m rooted_tree_classifier
112 121 122

Expected output is O(1)

python -m rooted_tree_classifier
121 131 212 323

Expected output is O(log*n)

python -m rooted_tree_classifier
112 121

Expected output is Θ(log n)

python -m rooted_tree_classifier
112 123 131

Expected output is Θ(log n)

python -m rooted_tree_classifier
121 212

Expected output is Ω(n)

Tests

To execute tests, run the following from the root directory:

python -m unittest discover