We give the first complexity-theoretic evidence for explicit constructions of objects such as rigid matrices (in the sense of Valiant) and Ramsey graphs on n vertices that do not have cliques or independent sets of size 2log(n). More generally, we give plausible complexity assumptions under which the Range Avoidance problem can be solved efficiently on uniform sequences of Boolean circuits - the non-uniform version was recently shown to be hard under standard cryptographic assumptions. As a by-product of our techniques, we construct hitting set generators against uniform algorithms with sub-logarithmic seed length, under plausible complexity assumptions as above.
(Based on joint work with Oliver Korten).
Short Bio:
Rahul Santhanam is Professor of Computer Science at University of Oxford, and Tutorial Fellow in Computer Science at Magdalen College. He completed his PhD in Computer Science at the University of Chicago in 2005, and after postdoctoral stints at Simon Fraser University and University of Toronto, was Lecturer (2008-2013) and then Reader (2013-2015) at the University of Edinburgh, before moving to Oxford. His work in mainly in computational complexity theory, with a particular interest in connections with other areas such as logic, algorithms, cryptography, learning and game theory.
