Guldo

Domains

Problems you can test speedups on

Each card is a problem we can measure speedups on, and says what size of speedup its test can prove. The built-in ones were set up by hand. The others were made by the compiler from a short description, and every number on their cards is read from the compiler's own record.

Compiled domains

Ready, with notes

dlog

solve(p, g, h): return an integer x with pow(g, x, p) == h, 0 <= x < p - 1. Any valid x counts; return None for no answer.

What it can prove: speedups from about 1.5 to 3 bits (2.8 to 8.0 times faster) than the baseline.

Usable, but read the compiler's notes below: they say how far to trust the test.

  • The test: problem sizes [28, 29, 30], 24 questions per size, time limit 120 s per question; about 3.07 CPU-hours to score one solver.
  • The baseline: the author has not said what it is or what is known to beat it, so a speedup over it may be easy.
  • Compiler self-test: passed. It checks that the baseline against itself scores about 0, that a solver which never answers scores 0, and that a known 1-bit speedup is recovered.

How often a real speedup of each size would be proven

Real speedup (bits)Proven in all three rounds%
00%
0.50%
10%
1.597%
2100%
3100%
460%
50%
60%

Assumes a solver's speed varies about 0.6 bit from question to question. The real figure is unknown until someone submits.

Notes from the compiler (4)
  • narrow ladder: 3 size(s) spanning 2.59 octaves of cost (3+ is needed for the estimator's three difficulty bins to be well populated): widen SIZE_RANGE or let the reference's cost grow faster
  • the first plan's cost predictions missed by more than an octave, so the ladder was re-planned from the confirming data: it is the best available but NOT independently confirmed
  • the cost model was still off by more than one octave at size(s) [30] after 2 refinements
  • the measured median at one size is 1.3 octaves from the smoothed trend (sampling noise at 16 instances per size): the power analysis uses the smoothed trend; raise --n-prof for a steadier profile

Version dlog-v1, fingerprint 4b6669a7acc6.

Check the compiler's arithmetic yourself (it recomputes the whole table from the saved record and says if anything differs):

python3 compile_domain.py recheck dlog
python3 submit_check.py my_solver.py --family dlog

Built-in families

Built in

gm: Lattice: a short vector

Given a lattice (a regular grid of points in many dimensions), find a short non-zero point on it. Each test lattice has a short point hidden in it, so a good answer is known to exist.

  • The test: problem sizes [64, 66, 68, 70, 72], 24 questions per size, time limit 120 s per question
  • Set up by hand, not by the compiler. What has been measured is on the Results page and its limits on the Limits page.
Built in

mlwe: Lattice: encryption-style

The same task on lattices of the kind used in some modern encryption schemes.

  • The test: problem sizes [97, 105, 113, 121, 129, 137], 12 questions per size, time limit 60 s per question
  • Set up by hand, not by the compiler. What has been measured is on the Results page and its limits on the Limits page.
Built in

factor: Integer factoring

Given a large number that is the product of two primes, find a factor of it.

  • The test: problem sizes [58, 60, 62, 64], 24 questions per size, time limit 120 s per question
  • Set up by hand, not by the compiler. What has been measured is on the Results page and its limits on the Limits page.

Add your own

You write three small pieces: how to make a test question from a secret number with the answer hidden inside (derive), how to check an answer exactly (verify), and a plain baseline solver. The first command below creates a working example to edit.

python3 compile_domain.py init mything
python3 compile_domain.py check mything
python3 compile_domain.py compile mything --quick
python3 compile_domain.py compile mything
python3 compile_domain.py show mything

New to this? The guide walks through it, including what the compiler checks, how to verify a certificate, and the limits.

What the compiler turns down

  • Questions that change depending on the clock, chance or the machine
  • A checker that accepts junk such as nothing, 0 or 1, or an answer read straight off the question
  • An answer hidden in the question text, or one answer that fits every question
  • A baseline that gets answers wrong, or that depends on the judge's own code

What it can't do

  • Judge whether your baseline is a good algorithm. A certificate only says "faster than this baseline"
  • Prove a problem has no shortcut
  • Prove speedups above about 5 bits (about 32 times faster) with a 120 s time limit