Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANNA GAL:
All reports by Author Anna Gal:

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-127 | 11th October 2014
Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

Batch Codes through Dense Graphs without Short Cycles

Consider a large database of $n$ data items that need to be stored using $m$ servers.
We study how to encode information so that a large number $k$ of read requests can be performed \textit{in parallel} while the rate remains constant (and ideally approaches one).
This problem is equivalent ... more >>>


TR14-122 | 30th September 2014
Eric Allender, Anna Gal, Ian Mertz

Dual VP Classes

Revisions: 2

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits ... more >>>


TR13-093 | 21st June 2013
Anna Gal, Jing-Tang Jang

A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for ... more >>>


TR12-172 | 8th December 2012
Mahdi Cheraghchi, Anna Gal, Andrew Mills

Correctness and Corruption of Locally Decodable Codes

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>


TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>


TR11-030 | 9th March 2011
Anna Gal, Andrew Mills

Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Locally decodable codes
are error correcting codes with the extra property that, in order
to retrieve the correct value of just one position of the input with
high probability, it is
sufficient to read a small number of
positions of the corresponding,
possibly corrupted ... more >>>


TR05-136 | 14th November 2005
Anna Gal, Michal Koucky, Pierre McKenzie

Incremental branching programs


In this paper we propose the study of a new model of restricted
branching programs which we call incremental branching programs.
This is in line with the program proposed by Cook in 1974 as an
approach for separating the class of problems solvable in logarithmic
space from problems solvable ... more >>>


TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

Boolean complexity classes vs. their arithmetic analogs


This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These ... more >>>


TR95-001 | 1st January 1995
Amos Beimel, Anna Gal, Michael S. Paterson

Lower Bounds for Monotone Span Programs

The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for ... more >>>




ISSN 1433-8092 | Imprint