All reports by Author Meera Sitharam:

__
TR97-048
| 13th October 1997
__

Soren Riis, Meera Sitharam#### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

__
TR96-049
| 9th September 1996
__

Per Enflo, Meera Sitharam#### Stable basis families and complexity lower bounds

__
TR96-030
| 31st March 1996
__

Meera Sitharam#### Approximation from linear spaces and applications to complexity

Soren Riis, Meera Sitharam

The semantics of decision problems are always essentially independent of the

underlying representation. Thus the space of input data (under appropriate

indexing) is closed

under action of the symmetrical group $S_n$ (for a specific data-size)

and the input-output relation is closed under the action of $S_n$.

more >>>

Per Enflo, Meera Sitharam

--

Scalar product estimates have so far been used in

proving several unweighted threshold lower bounds.

We show that if a basis set of Boolean functions satisfies

certain weak stability conditions, then

scalar product estimates

yield lower bounds for the size of weighted thresholds

of these basis functions.

Stable ...
more >>>

Meera Sitharam

We develop an analytic framework based on

linear approximation and point out how a number of complexity

related questions --

on circuit and communication

complexity lower bounds, as well as

pseudorandomness, learnability, and general combinatorics

of Boolean functions --

fit neatly into this framework. ...
more >>>