Papers

Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty

Topics: Human-Perceived Difficulty, SAT Solvers

This collaborative research investigates whether SAT solver metrics can predict human-perceived difficulty in Nonogram puzzles. Through a user study, the work compares solver statistics—including decisions, propagations, and conflicts—with participants’ reported difficulty and solving behaviour. The results find little evidence that these metrics align with either perceived difficulty or behavioural signals, while showing that participant expertise moderates the relationship between solver metrics and difficulty ratings. Analysis of solving trajectories and survey responses further reveals recurring human strategies, particularly complex constraint propagation, that are not captured by the solver metrics, highlighting a fundamental difference between human and computational measures of puzzle difficulty.

C. He, Y. Ju., A. Gao, J. Calver.

Submitted to AAAI 27; arXiv preprint (2026). arXiv: 2608.23300.

Revisiting Real-Time Interval and Throughput Maximization

Topics: Online Algorithms, Competitive Analysis

This collaborative research revisits real-time interval scheduling and throughput maximization, extending classical interval scheduling results to the more general throughput setting. The work develops new deterministic competitive algorithms for unweighted, proportionally weighted, and C-Benevolent throughput maximization under preemption–restart, introduces an advance-notice model that enables constant competitive guarantees without preemption, and establishes new bounds for the preemption–revoke model. In particular, it proves that no deterministic online algorithm can achieve a constant competitive ratio when processing times are unrestricted, while providing nearly tight lower and upper bounds for instances with a bounded number of distinct processing times.

A. Borodin, C. He, N. Mottu.

arXiv preprint (2026). arXiv: 2607.16163.

Revoke vs. Restart in Unweighted Throughput Scheduling

Topics: Online Algorithms, Competitive Analysis

This independent research investigates the preemption–revoke model for online throughput scheduling, where a running job may be aborted but cannot be restarted. The study proves that no deterministic online algorithm can achieve a constant competitive ratio in this setting. Using an adversarial construction that recursively embeds three-job instances, it shows that the ratio can be forced arbitrarily close to zero. The result contrasts sharply with the preemption–restart model, where a 1/2-competitive deterministic algorithm is known, highlighting how irrevocable revocation fundamentally limits online schedulability.

Supervised by Professor Allan Borodin at the University of Toronto.

C. He.

arXiv preprint (2025). arXiv: 2510.15318

Poster presented at the CSSU Undergraduate Research Conference, University of Toronto (2026). [View Poster]