Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR15-202 | 11th December 2015
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Building above read-once polynomials: identity testing and hardness of representation

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:
\item A deterministic polynomial-time non-black-box ... more >>>

TR14-180 | 22nd December 2014
Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Space-Efficient Approximations for Subset Sum

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 >>>

TR14-131 | 7th October 2014
Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

A game characterisation of tree-like Q-Resolution size

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 >>>

TR13-102 | 17th July 2013
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Small Depth Proof Systems

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint