Cody Murray

Research Fellow
Simon's Institute

Email:



I received my PhD from MIT and my Masters from Stanford, both under Ryan Williams, and I was an undergrad at UCSD.

Academic:

Publications:

In reverse chronological order.
Please observe the copyrights of these papers, whenever it is necessary to observe them.

2019
  • L. Chen, D. M. McKay, C. D. Murray, and R. R. Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems [ECCC]
    To appear in In 34th Computational Complexity Conference (CCC 2019).

  • D. M. McKay, C. D. Murray, and R. R. Williams. Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes [camera-ready pdf]
    To appear in 51st ACM Symposium on Theory of Computing (STOC 2019).


2018
  • C. D. Murray and R. R. Williams. Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP [pdf]
    In 50th ACM Symposium on Theory of Computing (STOC 2018).
    Also available on ECCC.


2017
  • C. D. Murray and R. Williams. Easiness Amplification and Uniform Circuit Lower Bounds [pdf]
    In 32nd Computational Complexity Conference (CCC 2017).


2015
  • C. Murray and R. Williams. On the (Non) NP-Hardness of Computing Circuit Complexity [pdf]
    Theory of Computing Volume 13 (2017) Article 4 pp. 1-22, 2017
    Also in 30th Conference on Computational Complexity (CCC 2015)


2013
  • L. Batman, R. Impagliazzo, C. Murray, and R. Paturi. Finding Heavy Hitters From Lossy or Noisy Data[pdf]
    APPROX 347-362