Guldo

Verified speedups, without trusting the claimant

Declare a problem. Get a challenge anyone can verify.

Someone says their algorithm is much faster than the standard one. How would you check? Describe the problem once. The compiler builds a fair test, runs it, and produces a report that anyone can re-check.

How we count speed: 3 bits faster means 8 times faster, and 10 bits means about 1,000 times. Each extra bit doubles it.

An illustration, not a result

Two solvers, the same questions

Say two people each write a program that factors big numbers. Both are given the same 100 numbers, made from a secret number that nobody could see in advance. The first program takes 40 seconds on the hard ones. The second takes 5. That is 8 times faster, or 3 bits. This site is a way for a stranger to confirm a claim like that without taking anyone's word for it.

Show what the compiler really prints

Real compiler output, for the dlog example

dlog: READY, WITH NOTES (read them: they say how far to trust the ladder)
  the challenge : sizes [28, 29, 30], CPU cap 120 s, 24 instances per size; one submission costs about 3.07 CPU-hours (worst case 14.4)
  it can certify: speedups from about 1.5 to about 3 bits over your reference
  self-test     : pass
  notes         : 4 (listed on the full card)

A shortened version of what python3 compile_domain.py show dlog prints. See the full card.

In that printout, the size ladder is the list of question sizes and the CPU cap is the time limit per question.

Start here

I have a problem

You can say exactly when an answer is right, and you have a plain solver to compare against. The compiler turns that into a fair test.

Compile your own

I have a faster solver

Write one Python file with a function called solve, check it locally, and see how it would be measured.

Go to Compete · Install the tool

I want to check a claim

You do not have to trust anyone. Recompute a result from its file, check a commitment yourself, or read what a result does not prove.

Read the guide · Check a commitment · What it does not show

From a declaration to a certificate

1

Describe the problem

Write three small pieces: how to make a test question from a secret number (with the answer hidden inside), how to check an answer exactly, and a plain baseline solver to compare against.

python3 compile_domain.py init mything
2

Compile it into a test

The compiler checks that your problem can't be gamed, times your baseline, picks the test sizes and time limit, and works out what size of speedup it can actually prove. It ends with READY or NOT READY.

python3 compile_domain.py compile mything
3

Get a certificate

After a round, one file holds the claim, the rules, the secret numbers and every raw measurement. Anyone can recompute the result from it, and checking it never runs the file's code unless you ask. It cannot show the CPU costs were honestly measured: that needs the verified sandbox, or re-running instances yourself.

python3 certificate.py verify x.cert.json

The compiler and certificates are built and tested, but no round has run on a verified sandbox yet, so no certificate here is official. Domains shows what each test can and can't prove; the guide explains how to write a problem and check a certificate.

How a test stays fair, in four steps

1

Commit

Before anyone submits, the judge publishes a fingerprint (a hash) of a secret number. Every test question is generated from that number, so nobody can prepare answers in advance, and the judge can't swap the questions afterwards.

2

Solve

The submitted solver and the baseline get the same questions, one process each, with a time limit. Every question has a known answer hidden inside it, so every one can be solved.

3

Check

Every answer is checked exactly. A wrong or missing answer is charged the full time limit, so giving up on the hard questions can't look like being fast.

4

Score

Questions are grouped by how hard the baseline found them. The score is a cautious estimate of the speedup on the hardest groups: a number we are 95% sure the true speedup is at least as large as. A lucky run can't inflate it.

A real run, end to end

The method on a real problem

Before the compiler existed, the method was tried by hand on lattice problems (geometry puzzles that modern cryptography relies on): a tuned solver against the stock one, on questions generated from a secret number that was fingerprinted first. This is that result. It is a real measurement, but it is not official, and it is one example of what a certificate would summarise.

The full run and its limits

Pre-registered, not official
2.6bits

A cautious estimate (we are 95% sure the true speedup is at least this) of how much faster a tuned lattice reducer solves hard questions than the stock one. The test and its pass mark were written down, with the secret number fingerprinted, before any data existed. Median speedup 4.1 bits; the exploratory hard-pool claim reads 2.9.

See the run

Where it stands

Done and testedThe testing method, three built-in problems (two lattice, one integer factoring), the compiler that makes more, speedup certificates, the judge, a pre-submission checker, the local submission portal and this site. Each has automated tests.
MeasuredA lattice test, with its pass mark written down before any data existed, met that mark. Re-timing it one job at a time moved the numbers by under 0.1 bits, in the cautious direction. The factoring check was different: running several jobs at once slowed the faster solver by over a bit, which is why running jobs side by side is listed as a hazard.
Measured, one criterion failedA check on a second problem where the right answer is known in advance: a fast factoring routine against the same method written as a plain loop, which should come out about 4.4 bits (about 21 times) faster. The method certified 4.1 bits (median 4.2). Pass marks written beforehand, a score of at least 2.5 and a median between 3.5 and 5.5, decide whether that counts as recovering it. The write-up is on the Pre-registrations page. The registered concurrency criterion failed: see Results.
Not doneThe locked-down environment for running other people's code has never been tested on a real machine, so no result can be official. An official result also needs three independent secret numbers. The code for this exists; the real-machine check does not.
Tested, not yet usedExact step counting (a cost that anyone can reproduce, instead of seconds), rounds that use it, and the extra claims on the Other claims page (a benchmark score, a verified negative result, a worst-case figure) pass their own tests on the author's computer, and the counter has been run for real on small programs. They have not been used in a real round, on a Linux server, or by anyone else, so expect rough edges.

Not only for lattices

Anything with an exact answer check

A problem fits if three things are true: an answer can be checked exactly and cheaply, test questions can be generated from a secret number, and there is a plain baseline solver to compare against. You write those three pieces; the compiler works out the rest. Lattice problems came first, and integer factoring second, as a check that the method recovers a speedup of a known size. Problems made with the compiler are listed on the Domains page.

What does not fit

  • No exact answer to check ("trains faster", "better quality")
  • Cost that isn't one process's CPU time (GPU, many machines, memory-bound)
  • Problems with no size where both solvers finish in reasonable time

Words used on this site

Bits
How we count speed. Each bit doubles it: 3 bits is 8 times faster.
Baseline (reference solver)
The plain, standard solver every other solver is compared against.
Instance
One test question. A solver gets it and must return an answer.
Size ladder
The list of question sizes used, from easier to harder.
Time limit (CPU cap)
The most CPU time one question may take. Failing or timing out is charged the full limit.
Seed and commitment
A secret number that every question is generated from, and its published fingerprint. The fingerprint proves the questions were fixed before anyone submitted.
Certificate
One file with the claim, the rules and every raw measurement, so anyone can recompute the result.
Official (certified)
A result measured inside the strict, locked-box test environment, on three independent secret numbers. Everything on this site is a practice result instead.
Locked box (sandbox)
A sealed environment that runs other people's programs so they cannot read the answers, hide work or tamper with the timer.
Round
One contest: the secret numbers are fingerprinted first, solvers are submitted until a deadline, then everything is run and the secrets are revealed.
Lattice, factoring, dlog
The puzzle types used so far: finding a short vector in a grid of points; splitting a big number into smaller ones; finding the exponent in a modular power (the discrete logarithm).
Exact count (step counting)
Counting the Python instructions a program runs instead of timing it. Anyone on the same Python version gets the same number, so nobody has to trust a clock or a computer.