קולוקוויום וסמינרים
כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
- CGGC Weekly Seminar
- Coding Theory Seminar
- Colloquia
- Hardware Security Seminar
- Pixel Club
- Theory of Data Science and Deep Learning
- Theory Seminar
קולוקוויום וסמינרים בקרוב
Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
- דובר:
- שיר כהן, הרצאה סמינריונית למגיסטר
- תאריך:
- יום שני, 10.8.2020, 11:00
- מקום:
- Zoom Lecture: https://technion.zoom.us/j/9479665459
- מנחה:
- Prof. Idit Keidar
King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of O˜(n) and O(1) expected time, breaking the O(n2) bit barrier for asynchronous Byzantine Agreement.
The Power of Implicit Acyclicity in the Enumeration Complexity of Database Queries
- דובר:
- נופר כרמלי, הרצאה סמינריונית לדוקטורט
- תאריך:
- יום ראשון, 16.8.2020, 11:00
- מקום:
- Zoom Lecture: https://technion.zoom.us/j/99974085218
- מנחה:
- Prof. Benny Kimelfeld
We inspect the fine-grained complexity of answering queries over relational databases. With the ideal guarantees, linear time is required before the first answer to read the input and determine its existence, and then we need to print the answers one by one. Consequently, we wish to identify the queries that can be solved with linear preprocessing time and constant or logarithmic delay between answers. A known dichotomy classifies CQs into those that admit such enumeration and those that do not. The computationally expensive component of query answering is joining tables, which can be done efficiently if and only if the join query is acyclic. However, the join query usually does not appear in a vacuum. For example, it may be part of a larger query, or it may be applied to a database with dependencies. We inspect how the complexity changes in these settings and chart the borders of tractability within. In addition, we consider the task of enumerating query answers with a uniformly random order, and we propose to do so using a random-access structure for representing the set of answers. We also prove conditional lower bounds showing that our algorithms capture all tractable queries in some cases. Among our results, we show that a union of tractable conjunctive queries may be intractable w.r.t. random access; on the other hand, a union of intractable conjunctive queries may be tractable w.r.t. enumeration. We also suggest an algorithm for generating tree decompositions that, in turn, can be used to simplify intractable queries by extracting an acyclic structure.
