Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Philipp Woelfel

We present a new lower bound technique for two types of restricted

Branching Programs (BPs), namely for read-once BPs (BP1s) with

restricted amount of nondeterminism and for (1,+k)-BPs. For this

technique, we introduce the notion of (strictly) k-wise l-mixed

Boolean functions, which generalizes the concept of l-mixedness ...
more >>>

Arnaldo Moura, Igor Carboni Oliveira

We propose a generalization of the traditional algorithmic space and

time complexities. Using the concept introduced, we derive an

unified proof for the deterministic time and space hierarchy

theorems, now stated in a much more general setting. This opens the

possibility for the unification and generalization of other results

that ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Jakob NordstrÃ¶m, Ning Xie

Properties of Boolean functions on the hypercube that are invariant

with respect to linear transformations of the domain are among some of

the most well-studied properties in the context of property testing.

In this paper, we study a particular natural class of linear-invariant

properties, called matroid freeness properties. These properties ...
more >>>

Richard Beigel, Bin Fu

The bin packing problem is to find the minimum

number of bins of size one to pack a list of items with sizes

$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects

a random element from the input list each time, we develop a

randomized $O({n(\log n)(\log\log n)\over ...
more >>>

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>