All reports by Author Karteek Sreenivasaiah:

__
TR16-153
| 28th September 2016
__

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah#### Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials

Revisions: 3

__
TR15-202
| 11th December 2015
__

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah#### Building above read-once polynomials: identity testing and hardness of representation

__
TR14-180
| 22nd December 2014
__

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Space-Efficient Approximations for Subset Sum

__
TR14-131
| 7th October 2014
__

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah#### A game characterisation of tree-like Q-Resolution size

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

The power symmetric polynomial on $n$ variables of degree $d$ is defined as

$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers

of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by

...
more >>>

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Polynomial Identity Testing (PIT) algorithms have focused on

polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted

formulas. Read-once polynomials (ROPs) are computed by read-once

formulas (ROFs) and are the simplest of read-restricted polynomials.

Building structures above these, we show the following:

\begin{enumerate}

\item A deterministic polynomial-time non-black-box ...
more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>