All reports by Author Rahul Santhanam:

__
TR21-159
| 15th November 2021
__

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams#### Constructive Separations and Their Consequences

__
TR21-138
| 23rd September 2021
__

Rahul Santhanam, Iddo Tzameret#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

__
TR21-039
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Algorithms and the Structure of Probabilistic Time

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

Rahul Santhanam, Iddo Tzameret

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>