Structures and methods for programmable memory address and decode circuits with low tunnel barrier interpoly insulators are provided. The decoder for a memory device includes a number of address lines and a number of output lines wherein the address lines and the output lines form an array. A number of logic cells are formed at the intersections of output lines and address lines. Each of the logic cells includes a floating gate transistor which includes a first source/drain region and a second source/drain region separated by a channel region in a substrate. A floating gate opposes the channel region and is separated therefrom by a gate oxide. A control gate opposing the floating gate. The control gate is separated from the floating gate by a low tunnel barrier intergate insulator. The low tunnel barrier intergate insulator includes a metal oxide insulator selected from the group consisting of PbO, Al.sub.2O.sub.3, Ta.sub.2O.sub.5, TiO.sub.2, ZrO.sub.2, Nb.sub.2O.sub.5 and/or a Perovskite oxide tunnel barrier.