Hierarchies, Circuit Lower Bounds and Pseudorandomness

  • Santhanam, Rahul (Principal Investigator)
  • 5 Conference contribution
Filter
Conference contribution

Search results

  • 2013

    On Medium-Uniformity and Circuit Lower Bounds

    Santhanam, R. & Williams, R., 2013, Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013. p. 15-23 9 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    File
  • 2012

    Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

    Jansen, M. J. & Santhanam, R., 24 Feb 2012, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. p. 519-530 12 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File

  • Marginal hitting sets imply super-polynomial lower bounds for permanent

    Jansen, M. J. & Santhanam, R., 2012, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012. ACM, p. 496-506 11 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 2011

    Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth

    Jansen, M. & Santhanam, R., 2011, Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Aceto, L., Henzinger, M. & Sgall, J. (eds.). Springer, p. 724-735 12 p. (Lecture Notes in Computer Science; vol. 6755).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Robust Simulations and Significant Separations

    Fortnow, L. & Santhanam, R., 2011, Automata, Languages and Programming : 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Springer, Vol. 6755. p. 569-580 12 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    File