אירועים
קולוקוויום וסמינרים
כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
קולוקוויום וסמינרים בקרוב
אור אבנת, הרצאה סמינריונית למגיסטר
A new fixed (non-adaptive) recursive scheme for multigrid algorithms is introduced. Governed by a positive parameter $\kappa$ called the cycle counter, this scheme generates a family of multigrid cycles dubbed $\kappa$-cycles. The well-known $V$-cycle, $F$-cycle, and $W$-cycle are shown to be particular members of this rich $\kappa$-cycle family, which satisfies the property that the total number of recursive calls in a single cycle is a polynomial of degree $\kappa$ in the number of levels of the cycle. This broadening of the scope of fixed multigrid cycles is shown to be potentially significant for the solution of some large problems on platforms, such as GPU processors, where the overhead induced by recursive calls may be relatively significant. In cases of problems for which the convergence of standard $V$-cycles or $F$-cycles (corresponding to $\kappa=1$ and $\kappa=2$, respectively) is particularly slow, and yet the cost of $W$-cycles is very high due to the large number of recursive calls (which is exponential in the number of levels), intermediate values of $\kappa$ may prove to yield significantly faster run-times. This is demonstrated in examples where $\kappa$-cycles are used for the solution of rotated anisotropic diffusion problems, both as a stand-alone solver and as a preconditioner. Moreover, a simple model is presented for predicting the approximate run-time of the $\kappa$-cycle, which is useful in pre-selecting an appropriate cycle counter for a given problem on a given platform. Implementing the $\kappa$-cycle requires making just a small change in the classical multigrid cycle.
מיכל פרידמן, הרצאה סמינריונית לדוקטורט
יום שלישי, 3.8.2021, 14:00
With the recent launch of the Intel Optane memory platform, non-volatile main memory in the form of fast, dense, byte-addressable non-volatile memory has now become available. Nevertheless, designing crash-resilient algorithms and data structures is complex and error-prone, especially when caches and machine registers are still volatile and the data residing in memory after a crash might not reflect a consistent view of the program state. This talk will present different approaches and transformations that adds durability to lock-free data structures, with a low performance overhead, which utilize and deal with all the complexities of the non-volatile main memory.
אלעד נחמיאס, הרצאה סמינריונית למגיסטר
יום ראשון, 8.8.2021, 11:00
Despite significant progress in software testing and verification, some undesired behaviors inevitably make their way to production. It is therefore common practice to interleave logging operations into modern software. Logging operations store information about the program's execution to help debugging and diagnosing problems. Usually, the programmer decides what parts of the program's state to log. This work aims to automatically complete logging operations in a given program based on learning from logging operations in other programs. Technically, we address the problem of predicting which variables to log at a given logging insertion point within the input program. This task arises challenges like following complicated semantic relations, which are long-range scattered over lengthy procedures. Our solution is based on recently studied deep-learning techniques from the scope of similar programming-related tasks. We suggest a novel modeling approach that involves both semantic characteristics, modeled by paths in the control-flow graph (CFG), and syntactic characteristics modeled by paths in the abstract syntax tree (AST). Our work is the first to leverage the effective paths-based modeling approach for both semantic and syntactic relations. We compare our approach to a wide variety of other known representations. Our experiments show that our model is more scalable and effective than the other methods.
עידו רפאל, הרצאה סמינריונית למגיסטר
יום שלישי, 10.8.2021, 10:30
מנחה: Prof. Y. Emek & Prof. S. Kutten
We improve the message efficiency of the time-efficient construction of a "small" (i.e. universaly optimal) k-dominating set (k-DS) under the Distributed CONGEST model.
This task was suggested by Kutten and Peleg as a useful primitive in constructing other time-efficient algorithms such as a minimum spanning tree.
It is also useful for constructing other local (i.e. sub-diameter time) algorithms such as partitioning the network into clusters (each a rooted tree) of diameter k.
We first address the problem in the KT1 model (where a node knows the unique identity of each neighbor) that has been receiving increased attention in recent years.
The new algorithm achieves time \tilde{O}(k^2) and message \tilde{O}(nk) complexities.
It is thus the first small k-DS algorithm with o(m) messages (for k=o(m/n)) in the KT1 model.
We also address the KT0 model used by Kutten and Peleg (where a node does not know the identities of its neighbors).
For KT0, we present the first asynchronous sub-diameter time algorithm.
Its message complexity is \tilde{O}(m+nk), compared to the O(m k log*n) complexity of the trivial asynchronous algorithm (that uses an alpha-synchronizer).
בהגת קעואר, הרצאה סמינריונית למגיסטר
יום שלישי, 24.8.2021, 10:30
Inverse problems in image processing refer to a family of problems in which we aim to recover an original signal given degraded measurements of it. Various techniques and algorithms have been suggested for general inverse problems, with a special emphasis dedicated to the most prominent example -- image denoising. Recent deep neural network approaches for these tasks focus on minimizing the mean squared error (MSE) between the original and the reconstructed signals. However, in moderate to severe degradation conditions, an MSE minimizer (MMSE) produces blurry, washed-out reconstructions.
In our work we introduce an alternative approach for solving inverse problems: Sampling from the posterior distribution of the signal given the degraded measurements. We present a novel stochastic algorithm that samples from the posterior, starting image denoising and inpainting, and generalizing this approach to general inverse problems. The developed algorithm in our work is based on Langevin dynamics and Newton's method in optimization. Due to its stochasticity, the proposed algorithm can produce a variety of outputs for a given input, all shown to be legitimate results, achieving a significantly higher perceptual quality than the MMSE counterpart. In this self-contained talk we will present the necessary background on Langevin dynamics, and describe our novel algorithm, along with the intricate mathematical derivations that led to its success. We will also demonstrate its results on various inverse problems, such as image denoising, inpainting, deblurring, super resolution, and compressive sensing.
אופיר גורדון, הרצאה סמינריונית למגיסטר
יום חמישי, 2.9.2021, 14:00
The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity.
Our analysis is based on two complementary approaches: In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)---a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length.
In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence.
Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least 2 to the power of 10,000,000.
