Colloquium

The IDC CS Colloquium
 

Gil Kalai - Understanding linear programming and the simplex algorithm

Linear programming is the problem of maximizing a linear function φ subject to a system of linear inequalities. The solutions to these linear inequalities form a convex polyhedron P (called the feasible polyhedron") and Dantzig's simplex algorithm from the early 50s, can be described geometrically as moving from one vertex to an adjacent vertex of P. 

 

In the lecture, I will  overview some developments regarding linear programming and the simplex algorithms and present some outstanding problems. 

Among these problems: 

09/05/2024 - 13:30

Aryeh Kontorovich - Learning infinitely many coins simultaneously

Inferring the bias of a single coin from independent flips is a well-understood problem, technically known as estimating the Bernoulli parameter p. In particular, how the sample size (number of flips) n, the precision ε, and the confidence δ constrain each other is known within tight upper and lower bounds. When we want to estimate the bias of d coins simultaneously, this problem is well-understood as well, at least in the worst case over the Bernoulli parameters pᵢ. What if we want to estimate infinitely many pᵢ's simultaneously?

02/05/2024 - 13:30

Alon Rashelbach - Trading Memory Accesses for Computations in Packet Processing (and Beyond)

Range matching, the process of identifying a range that contains a given input number, is vital in various computer systems, like networking, security, and storage. However, the current methods for range matching hit a wall when it comes to handling a larger number of supported ranges without slowing down search performance: they heavily rely on pointer-chasing algorithms, causing issues when their data structures outgrow the CPU core cache.

11/04/2024 - 13:30

Yosi Shacham - Bio-convergence: when engineering meets

Bio-convergence is combining the knowledge and technologies in the fields of biology and life sciences with that of engineering and computer sciences. It includes both concepts from Information and Communication technologies (e.g. microelectronics, MEMS, algorithms, systems etc.) with life science. Bio-convergence can be treated as a new field or an approach, that is growing at an accelerated rate affecting both academia and the global industry. It greatly affects medicine and medical sciences, the environment, energy, agriculture, food, security, and other sectors.

04/04/2024 - 13:30

Guy Gaziv - Strong and Precise Modulation of Human Percepts via Robustified ANNs

The visual object category reports of artificial neural networks (ANNs) are notoriously sensitive to tiny, adversarial image perturbations. Because human category reports (aka human percepts) are thought to be insensitive to those same small-norm perturbations — and locally stable in general — this argues that ANNs are incomplete scientific models of human visual perception. Consistent with this, we show that when small-norm image perturbations are generated by standard ANN models, human object category percepts are indeed highly stable.

22/02/2024 - 11:30

Eyal Ofek - Work-Verse: Using augmentation of user’s senses, and scene understanding to enable a more inclusive workspace

 the one hand, people may work at flexible hours, independent of traffic limitations, but on the other hand, they may need to work in makeshift spaces with less-than-optimal working conditions; applications are not flexible to their physical and social context and remote collaboration do not account for the difference between the user's conditions and capabilities.

31/07/2023 - 10:00

Eitan Yaakobi - The Applications of Constrained Systems in DNA Storage: Efficient Synthesis and DNA Labeling

DNA-based storage has attracted significant attention due to recent demonstrations of the viability of storing information in macromolecules. Given the trends in cost decreases of DNA synthesis and sequencing, it is estimated that within the next decade DNA storage may become a highly competitive archiving technology. This technology introduces new challenges in finding coding solutions to address various problems associated with the implementation of DNA-based storage systems.

15/06/2023 - 13:30

Alon Kipnis - Detecting Some Human Edits of AI-Generated Text with Information Theory and Higher Criticism

We address the question of whether a given article is the output of a generative language model or perhaps includes some significant edits by a different author, possibly a human. For this problem, we develop a detection method that involves many perplexity tests for the origin of individual sentences, combining these multiple tests into a global test of significance using Higher Criticism (HC). As a by-product, we can identify sentences or other text chunks suspected as generated by a different mechanism than the language model.

18/05/2023 - 13:30