[an error occurred while processing this directive]<meta name="keywords" content="Department of Computer Science, publications, by bibtex, Rahul Santhanam"></meta><meta name="description" content="Publications, by bibtex, Department of Computer Science, Oxford, Rahul Santhanam"></meta><title>Department of Computer Science, University of Oxford: Rahul Santhanam : Publications
</title><style type="text/css">
			  .btn-toolbar::after, .btn-toolbar::before
			  {
			    content: " ";
			    display: table;
			  }

			
			.btn-toolbar
			{
			    margin-bottom: 2em;
			}

			  .btn-toolbar::after, .btn-group::after
			  {
			    clear: both;
			  }


			.btn-toolbar .btn, .btn-toolbar .btn-group
			  {
			    float: left;
			}
			
			.btn-group
			  {
			    display: inline-block;
			    position: relative;
			    vertical-align: middle;
			}

			  .btn-group > .btn:first-child:not(:last-child)
			  {
			    border-bottom-right-radius: 0;
			    border-top-right-radius: 0;
			}
			
			.btn-group > .btn:first-child
			  {
			    margin-left: 0;
			}

			.btn-group > .btn
			  {
			    float: left;
			    position: relative;
			}

			  .btn-group > .btn:not(:first-child):not(:last-child)
			  {
			    border-radius: 0;
			}
			
			  .btn-group > .btn:last-child:not(:first-child)
			  {
			    border-bottom-left-radius: 0;
			    border-top-left-radius: 0;
			}
			
			.btn-group .btn + .btn, .btn-group .btn + .btn-group, .btn-group .btn-group + .btn, .btn-group .btn-group + .btn-group
			  {
			    margin-left: -2px;
			}
			</style>[an error occurred while processing this directive]<div class="content-width"><ol class="breadcrumb text-uppercase"><li><a href="/">Home</a></li><li><a href="/aboutus/">About Us</a></li><li><a href="/people/">People</a></li><li><a href="/people/faculty.html">Faculty</a></li><li><a href="/people/Rahul.Santhanam"><span itemprop="name">Rahul Santhanam</span></a></li><li class="active">Publications</li></ol></div><!-- MOBILE NAVIGATION --><div class="content-width space-below mobile-menu-placeholder visible-xs visible-sm"></div><!-- COLUMNS --><div class="container-fluid content-width"><div class="row"><div class="col-xs-12 col-md-9 col-md-push-3" id="maincontent"><!-- CONTENT (Column 2) --><div class="page-title"><h1>Rahul Santhanam : Publications
</h1></div><div role="toolbar" class="btn-toolbar"><div class="btn-group"><a href="/people/publications/date/Rahul.Santhanam.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-sort-by-attributes"></span> By date</a><a href="/people/publications/title/Rahul.Santhanam.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-sort-by-attributes"></span> By title</a><a href="/people/publications/type/Rahul.Santhanam.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-sort-by-attributes"></span> By type</a><a href="/people/publications/bibtex/Rahul.Santhanam.html" aria-hidden="true" type="button" class="btn btn-oxford-blue"><span class="glyphicon glyphicon-file"></span> BibTex</a></div></div><p></p><p>Click <a href="/people/publications/bibtex/Rahul.Santhanam.bib">here</a> to download all publications in a single bibtex file</p><pre>
@inproceedings{10368,
  title = "Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability",
  author = "Rahul Santhanam",
  year = "2010",
  journal = "Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science",
}</pre><pre>
@inproceedings{10369,
  title = "Infeasibility of Instance Compression and Succinct PCPs for NP",
  author = "Rahul Santhanam and Lance Fortnow",
  year = "2008",
  journal = "Proceedings of the 40th Annual ACM Symposium on Theory of Computing",
}</pre><pre>
@inproceedings{10370,
  title = "Circuit Lower Bounds for Merlin-Arthur Classes",
  author = "Rahul Santhanam",
  year = "2007",
  journal = "Proceedings of the 39th Annual ACM Symposium on Theory of Computing",
}</pre><pre>
@inproceedings{10371,
  title = "Hierarchy Theorems for Probabilistic Polynomial Time",
  author = "Rahul Santhanam and Lance Fortnow",
  year = "2004",
  journal = "Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science",
}</pre></div><div class="col-xs-12 col-md-3 col-md-pull-9 side-menu-col"><h2 class="side-menu-title text-uppercase"><a href="#">About Us</a></h2><ul class="side-menu"><li class="active mobile-menu-source"><a href="/people/">People</a><ul><li class="active"><a href="/people/faculty.html">Faculty</a></li><li><a href="/people/research.html">Research</a></li><li><a href="/people/students.html">Students</a></li><li><a href="/people/support.html">Professional Services</a></li><li><a href="/people/visitingprofessors.html">Visiting Professors</a></li><li><a href="/people/emeritusfaculty.html">Emeritus Faculty</a></li></ul></li><li><a href="/aboutus/vacancies/">Vacancies</a></li><li><a href="/aboutus/women-cs-oxford/index.html">Women in the department</a></li><li><a href="/aboutus/equality-diversity-inclusion/index.html">Equality, diversity and inclusion</a></li><li><a href="https://www.alumniweb.ox.ac.uk/cs/make-a-donation">Support Us</a></li><li><a href="/aboutus/cshistory.html">Our History</a></li><li><a href="/aboutus/contact.html">Contact Us</a></li></ul></div></div></div>[an error occurred while processing this directive]