Detlef Sieling

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have

been suggested as a generalization of OBDDs for the representation and

manipulation of Boolean functions. Instead of variables as in the

case of OBDDs parities of variables may be tested at the nodes of an

LTOBDD. By this extension it is ...
more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Charanjit Jutla, Vijay Kumar, Atri Rudra

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>