Topic: Computational complexity

Oren Renard studies security of quantum position verification based on f-routing. The work derives resource lower bounds for uniformly generated attackers by connecting successful attacks to the computational complexity of the routed function. Separate results cover arbitrary quantum channels, Pauli-sparse unitaries and Clifford+T circuits. Time and space hierarchies yield explicit functions secure against polynomial or quasipolynomial numbers of attacker qubits under these computational restrictions, extending earlier bounds while increasing the complexity of honest evaluation.

Cristopher Moore connects computational complexity to questions about cognition and artificial intelligence. The discussion considers what makes a problem difficult, how rugged landscapes shape computation, and what complexity theory can contribute to understanding learning and generalization in brains and machines.