10 citations · 14 across the 10 of their papers we have counts for
12 papers
Automated Template-free Synthesis of Instruction-Centric Leakage Contracts for Black-Box CPUs
Elvira Moreno, Tiziano Marinaro, Ryan Williams +4
Side-channel attacks pose a significant security threat for modern computing platforms, because they exploit subtle discrepancies in CPU behaviors to leak sensitive information. To…
Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries
Hanlin Ren, Ryan Williams
We prove a near-maximum () circuit lower bound for the complexity class , corresponding to exponential time with access to a promis…
Beating Trivial Time for Tricky Triangle Tasks
Neha Pant, Ryan Williams
For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-graine…
Simulating Time With Square-Root Space
R. Ryan Williams
We show that for all functions , every multitape Turing machine running in time can be simulated in space only . This is a substantial improvem…
Reframing the Mind-Body Picture: Applying Formal Systems to the Relationship of Mind and Matter
Ryan Williams
This paper aims to show that a simple framework, utilizing basic formalisms from set theory and category theory, can clarify and inform our theories of the relation between mind an…
Parallel Play Saves Quantifiers
Marco Carmosino, Ronald Fagin, Neil Immerman +4
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear o…