All reports by Author Anna Gal:

__
TR22-143
| 7th November 2022
__

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny#### Certificate games

Revisions: 1

__
TR22-059
| 27th April 2022
__

Siddhesh Chaubal, Anna Gal#### Diameter versus Certificate Complexity of Boolean Functions

__
TR20-134
| 9th September 2020
__

Siddhesh Chaubal, Anna Gal#### Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

__
TR19-128
| 24th September 2019
__

Anna Gal, Robert Robere#### Lower Bounds for (Non-monotone) Comparator Circuits

__
TR19-006
| 17th January 2019
__

Anna Gal, Ridwan Syed#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

__
TR18-205
| 3rd December 2018
__

Siddhesh Chaubal, Anna Gal#### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

__
TR18-160
| 12th September 2018
__

Anna Gal, Avishay Tal, Adrian Trejo NuĂ±ez#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

__
TR14-180
| 22nd December 2014
__

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

__
TR14-127
| 11th October 2014
__

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song#### Batch Codes through Dense Graphs without Short Cycles

__
TR14-122
| 30th September 2014
__

Eric Allender, Anna Gal, Ian Mertz#### Dual VP Classes

Revisions: 2

__
TR13-093
| 21st June 2013
__

Anna Gal, Jing-Tang Jang#### A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

__
TR12-172
| 8th December 2012
__

Mahdi Cheraghchi, Anna Gal, Andrew Mills#### Correctness and Corruption of Locally Decodable Codes

Revisions: 1

__
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

__
TR11-030
| 9th March 2011
__

Anna Gal, Andrew Mills#### Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

__
TR05-136
| 14th November 2005
__

Anna Gal, Michal Koucky, Pierre McKenzie#### Incremental branching programs

__
TR95-049
| 19th October 1995
__

Anna Gal, Avi Wigderson#### Boolean complexity classes vs. their arithmetic analogs

__
TR95-001
| 1st January 1995
__

Amos Beimel, Anna Gal, Michael S. Paterson#### Lower Bounds for Monotone Span Programs

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

Siddhesh Chaubal, Anna Gal

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we ... more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most

polynomial in sensitivity for any Boolean function.

Until a recent breakthrough of Huang, the conjecture had been

wide open in the general case,

and was proved only for a few special classes

of Boolean functions.

Huang's result implies that block ...
more >>>

Anna Gal, Robert Robere

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and ... more >>>

Anna Gal, Ridwan Syed

We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity ... more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>

Anna Gal, Avishay Tal, Adrian Trejo NuĂ±ez

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... 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 >>>

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

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

Eric Allender, Anna Gal, Ian Mertz

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

Anna Gal, Jing-Tang Jang

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

Mahdi Cheraghchi, Anna Gal, Andrew Mills

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

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

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

Anna Gal, Andrew Mills

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

Anna Gal, Michal Koucky, Pierre McKenzie

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

Anna Gal, Avi Wigderson

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

Amos Beimel, Anna Gal, Michael S. Paterson

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