Publications

Computational Complexity

  • With Harry Buhrman, Subhasree Patro, and Florian Speelman. Memory compression with quantum random-access gates. (TQC 2022 proceedings, ArXiv)
  • With Harry Buhrman, Subhasree Patro, and Florian Speelman. Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. (TQC 2021 workshop, QIP 2022 workshop, ITCS 2022 proceedings, ArXiv)
  • With Shuichi Hirahara and Rahul Ilango. Hardness of Constant-round Communication Complexity. CCC 2021. (ECCC)
  • With Pavel Dvořák. Lower Bounds for Semi-adaptive Data Structures via Corruption. FCTTCS 2020. (arXiv)
  • With Rahul Ilango and Igor Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions. CCC 2020. (ECCC, detailed 2h talk )
  • With Sagnik Mukhopadhyay. Lifting theorems for equality. STACS 2019. (ECCC)
  • With Arkadev Chattopadhyay, Michal Koucký and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. Computational Complexity, 2019. (ArXiV, Springer)
  • With Arkadev Chattopadhyay, Michal Koucký and Sagnik Mukhopadhyay. Simulation Beats Richness: New Data-Structure Lower-Bounds. STOC 2018. (Conference version, ECCC)
  • With Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký and Sagnik Mukhopadhyay. Lower Bounds for Elimination via Weak Regularity. STACS 2017. (ECCC)
  • With Harry Buhrman, Michal Koucký, and Florian Speelman. Catalytic Space: non-determinism and hierarchy. STACS 2016. (pdf)
  • With Harry Buhrman, Richard Cleve, Michal Koucký and Florian Speelman. Computing on a full memory: Catalytic Space. STOC 2014. (pdf, video, slides)
  • With Harry Buhrman and Leen Torenvliet. Hardness of approximation for knapsack problems. Theory of Computing Systems, 2014. (pdf)
  • With Joshua Brody, Harry Buhrman, Michal Koucký, Florian Speelman and Nickolay Vereshchagin. Towards a reverse Newman’s theorem in interactive information complexity. CCC 2013. Journal version published in Algorithmica. (pdf)
  • With Eric Allender, Harry Buhrman and Luke Friedman. Reductions to the set of random strings: The resource-bounded case. MFCS 2012. Journal version published in Logical Methods in Computer Science. (pdf)
  • With Harry Buhrman, Lance Fortnow and John M. Hitchcock. Learning reductions to sparse Sets. MFCS 2013. (pdf)
  • With Harry Buhrman, Lance Fortnow and Michal Koucký. Derandomizing from random strings. CCC 2010. (pdf)
  • With Amir M. Ben-Amram and Isabel Oitavem. Monotonicity constraints in characterizations of PSPACE. Journal of Logic and Computation, 2012. (pdf)

Formal Languages

  • With Nelma Moreira and Rogério Reis. The computational power of parsing expression grammars. Presented at DLT 2018. Published on the Journal of Computer and System Sciences in 2020. (ArXiv, JCSS)

Computability and Logic

  • A tese de Church–Turing. Boletim da Sociedade Portuguesa de Matemática, 2012. (pdf)
  • With Edwin Beggs, José Félix Costa, and John V. Tucker. Computational complexity with experiments as oracles II: Upper bounds. Proceedings of the Royal Society of London A, 2009.
  • With José Félix Costa and Jerzy Mycka. A foundation for real recursive function theory. Annals of Pure and Applied Logic, 2009. (pdf)
  • With José Félix Costa. Five views of hypercomputation. International Journal of Unconventional Computing, 2009. (pdf)
  • With Edwin Beggs, José Félix Costa, and John V. Tucker. Computational complexity with experiments as oracles. Proceedings of the Royal Society of London A, 2008.
Advertisement