Ramamohan Paturi

A professor of computer science at the University of California, San Diego, known for k-SAT algorithms and the Exponential Time Hypothesis.

1 articleLast mentioned

Ramamohan Paturi is a theoretical computer scientist and a professor of computer science at the University of California, San Diego. His research focuses on computational complexity theory and algorithms for satisfiability problems.

With Russell Impagliazzo he proposed the Exponential Time Hypothesis (ETH), and he is a co-author of the PPZ and PPSZ algorithms, which solve k-SAT faster than exhaustive 2^n search.

This entry is based on AIPOST articles and widely known facts. If something is wrong, please send us a correction request.

Articles covering this entry

  • ETH Disproof by OpenAI's AI: What Changes for P vs NP and CryptographyAI News ·

    …hypothesis, proposed roughly three decades ago by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, asserted that solving the k-CNF version of this probl…

    Read article

Found a mistake or missing an entry?

Wiki entries are based on AIPOST articles and widely known facts. If an entry is wrong, send us a correction request and we will check and fix it. Names from new articles are added to the wiki after the article is published.