All reports by Author Ramamohan Paturi:

__
TR15-148
| 9th September 2015
__

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

__
TR14-024
| 19th February 2014
__

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider#### 0-1 Integer Linear Programming with a Linear Number of Constraints

__
TR04-004
| 13th January 2004
__

Ramamohan Paturi, Pavel Pudlak#### Circuit lower bounds and linear codes

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the

number of variables and $cn$ is the number of constraints. The key ...
more >>>

Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>