קולוקוויום וסמינרים

We consider a variant of reachability in Vector Addition Systems (VAS) dubbed box reachability, whereby a vector v in N^d is box-reachable from 0 in a VAS V if V admits a path from 0 to v that not only stays in the positive orthant (as in the standard VAS semantics), but also stays below v, i.e., within the ׳׳box׳׳ whose opposite corners are 0 and v.

Our main result is that for two-dimensional VAS, the set of box-reachable vertices almost coincides with the standard reachability set: the two sets coincide for all vectors whose coordinates are both above some threshold W. We also study properties of box-reachability, exploring the differences and similarities with standard reachability.

Technically, our main result is proved using powerful machinery from convex geometry.

Error-correcting codes are central to information theory and theoretical computer science, enabling reliable communication in the presence of noise. Classical results focus primarily on substitutions and erasures, and over the years elegant constructions have emerged that meet, or closely approach, the optimal rate–noise tradeoffs in these settings. A natural and equally fundamental error model involves synchronization errors, such as insertions and deletions. These errors, already studied in the 1960s, cause misalignment between sender and receiver and arise in various modern technologies, with DNA-based data storage being a particularly compelling example. Despite decades of attention, fully characterizing the capacity of synchronization channels and constructing practical, near-optimal codes for them remain major open challenges.
In this talk, I will survey recent progress on coding for synchronization channels and then focus on the performance of linear and Reed–Solomon codes under insertions and deletions, demonstrating that well-structured algebraic codes can, perhaps unexpectedly, correct a significant amount of synchronization noise. I will then highlight a surprising application of these ideas in secret sharing. Finally, I will discuss how input-correlated insertion/deletion channels naturally arise in DNA-based data storage, an emerging ultra-dense archival technology, and present capacity theorems and efficient coding schemes tailored to an important class of such channels.

Short Bio: Roni Con is a postdoctoral researcher at the Technion, hosted by Prof. Eitan Yaakobi. In Spring 2024, he was a Simons Research Fellow in the program Error-Correcting Codes: Theory and Practice at the Simons Institute for the Theory of Computing. He completed his Ph.D. in October 2023 at Tel Aviv University under the supervision of Profs. Amir Shpilka and Zachi Tamo. His research focuses on error-correcting codes and information theory, with applications to synchronization-error channels, modern storage systems, and cryptography.

I will discuss recent work highlighting the importance of selecting an appropriate geometric representation for tasks such as 3D/4D generation, medical imaging, and motion capture.  I will argue that this choice should follow directly from the problem’s inherent constraints and the desired outcomes.

Expanders are graphs that are both edge-sparse and well connected. They have been an instrumental tool in many results in mathematics and computer science, some of which seem to have little connection to graphs at all. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs — sparse and well connected hypergraphs.  HDXs have already played a key role in several recent results in theoretical computer science and combinatorics. However, much of their underlying theory remains unexplored.

Motivated by this, we will see what HDXs are, why they generalize expander graphs, and how they serve as a common setting for results in probability and computational complexity. 

I will illustrate their power by presenting new Chernoff-type inequalities for HDXs and explaining their applications to: 

1. Hardness amplification - constructing functions for which the best polynomial-time algorithm performs no better than random guessing.

2. Hardness of approximation - constructing natural problems for which even approximate solutions are intractable unless P=NP.

The talk will not assume prior background and is aimed at a broad audience. 

Bio: Yotam is a theoretical computer scientist working between combinatorics and computational complexity. His work studies combinatorial structures such as high-dimensional expanders, and their implications for algorithms and complexity theory. He is currently a postdoc fellow at the Institute for Advanced Study and received his PhD from the Weizmann Institute of Science.

I will present an overview of some topics in computational (and combinatorial, and a bit algebraic) geometry, that constitute milestones in the work in this area by myself and by many colleagues and (former) students in the past 45 years. The topics include, as time permits, algorithmic motion planning, arrangements, lower envelopes, incidences, space decomposition, polynomial partitioning, and more. 

Bio: Micha Sharir received his Ph.D. in Mathematics from Tel Aviv University in 1976, and then switched to Computer Science, doing his postdoctoral studies at the Courant Institute of New York University. He returned to Tel Aviv University in 1980, and has been there, at the School of Computer Science, ever since. He is also a visiting research professor at the Courant Institute, where he has been the deputy head of the Robotics Lab (1985-89). He has served as the head of the Computer Science Department (twice) and as the head of the School of Mathematics (1997-99). He is one of the co-founders of the Minerva Center for Geometry at Tel Aviv University. 

His research interests are in computational and combinatorial geometry and their applications. He has pioneered (with Jack Schwartz) the study of algorithmic motion planning in robotics during the early 1980s, and has been involved in many fundamental research studies that have helped to shape the fields of computational and combinatorial geometry. Among his major achievements, in addition to his earlier work on robotics, are the study of Davenport-Schinzel sequences and their numerous geometric applications, the study of geometric arrangements and their applications, efficient algorithms in geometric optimization (including the introduction and analysis of generalized linear programming), and the study of combinatorial problems involving point configurations, including, since 2008, the application of algebraic techniques to problems involving incidences, distinct and repeated distances, and other related problems in combinatorial and computational geometry. 

His work won him several prizes, including a Max-Planck research prize (1992, jointly with Emo Welzl), the Feher Prize (1999), the Mif'al Hapais' Landau Prize (2002), and the EMET Prize (2007). He is the incumbent of the Nizri Chair in computational geometry and robotics, a Fellow of the Association for Computing Machinery (since 1997), has an honorary doctorate degree from the University of Utrecht (1996), and is a member of the Israeli Academy of Sciences and Humanities (2018). He has supervised 27 Ph.D. students, many of which are now at various stages of an academic career, in Israel and abroad. 

Technion host: Sarah Keren

We introduce a vision-guided robotic system for automated saffron flower harvesting. Using camera-based perception and robotic manipulation, the system detects and cuts whole flowers while preserving their stigmas and avoiding plant damage.