^February March – 2012 ^April

A novel approach is suggested for reducing traffic conflicts in at-grade (2D) urban networks. Intersections without primary vehicular conflicts are defined as zero traffic conflict (ZTC) designs. Complete classification of maximal ZTC designs is presented, including designs that combine driving on the right side in some streets and driving on the left side in other streets. It is proved that there are 9 four-way and 3 three-way maximal ZTC intersection designs, to within mirror, rotation, and arrow reversal symmetry. Vortices are used to design networks where all or most intersections are ZTC. Increases in average travel distance, relative to unrestricted intersecting flow, are explicitly calculated for grid-networks of sizes 10 by 10, 10 by 20 and 20 by 20 nodes with evenly distributed origins and destinations. The exact increases depend primarily on various short-range conditions, such as the access to the network. The average distance increase in most cases examined is up to four blocks. These results suggest that there is a potential for the new designs to be relevant candidates in certain circumstances, and that further study of them is worthwhile.

While many of the classical codes are cyclic, a long standing conjecture asserts that there are no 'good' cyclic codes. In recent years the intrest in symmetric codes has been promoted by Kaufamn, Sudan, Wigderson and others (where symmetric means that the acting group can be any group). Answering their main question (and in contrary to the common expectation), we show that there DO exist symmetric good codes. In fact, our codes satisfy all the "golden standards" of coding theory. Our construction is based on the Ramanujan graphs contructed by Lubotzky-Samuels-Vishne as a special case of Ramanujan complexes. The crutial point is that these graphs are edge transitive and not just vertex transitive as in prevous constructions of Ramanujan graphs. All notions will be explained. Joint work with Tali Kaufman.

We contribute a further step towards the plausible real time construction of suffix trees by presenting an on-line algorithm that spends O(log log n) time processing each input symbol and takes O(n log log n) time in total. Our results improve on a previously published algorithm that take O(log n) time per symbol and O(n log n) time in total. The improvements are achieved using a new data structure for the fringe marked ancestor problem, a special case of the nearest marked ancestor problem, which may be of independent interest. Joint work with Pino Italiano, University of Rome.