Next

__
TR18-040
| 21st February 2018
__

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan#### Non-Malleable Codes for Small-Depth Circuits

__
TR18-039
| 23rd February 2018
__

Md Lutfar Rahman, Thomas Watson#### Complexity of Unordered CNF Games

__
TR18-038
| 21st February 2018
__

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann#### Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees

Next

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann

This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.

The key notion for understanding the ... more >>>

Next