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

כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.


Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.

Academic Calendar at Technion site.

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

  • Theory Seminar: On Computing Multilinear Polynomials Using Depth Four Circuits of Bounded Individual Degree

    דובר:
    Suryajith Chillara (University of Haifa)
    תאריך:
    יום רביעי, 28.10.2020, 12:30
    מקום:
    Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code

    The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within P. In this talk, we will talk about the complexity of computing an entry in the product of d many n×n generic matrices (denoted IMMn,d) by depth four circuits of bounded individual degree.

    We show that for all r ≤ na for a fixed constant a, any “syntactic” depth four circuit of bounded individual degree r computing IMMn,d must have size n𝛺(√d) when d ≤ nb (for a fixed constant b ≤ a). This improves upon a previous result of Kayal, Saha and Tavenas [STOC 2016 & Theory of Computing, 2018] who proved a lower bound of (n/r1.1)𝛺(√d/r) for the same.

    This talk assumes no relevant background. We will introduce the model of computation, the motivation to study computation of multilinear polynomials by circuits of bounded individual degree and briefly survey relevant results to this restricted model of computation.

    More details.

  • מיומנו של מראיין סדרתי - המדריך להכנה (נכונה) לראיונות טכניים

    From the Diary of a Serial Interviewer - Preparing (Correctly) for Technical Interviews

    תאריך:
    יום שלישי, 3.11.2020, 19:00
    מקום:
    שידור ישיר בזום (פרטים לאחר הרשמה)

    הנכם מוזמנים להרצאה ושיחה עם איתי רוזנבלט, ראש קבוצה ומוביל טכני ב-scaleIO ומייסד שותף וסמנכ"ל מו"פ בסטארט-אפ חדש, אשר יעסקו בנושא הראיון הטכני ובמרכיבי ההצלחה והרושם הראשוני שהוא מעניק:
    • מה המראיין מחפש בכל חלק מהראיון
    • מה ההזדמנות שלך כמועמד
    • איך להתכונן

    ההרצאה תתקיים יום שלישי, 3 בנובמבר, 2020, בשעה 19:00, באמצעות זום (קישור יישלח לאחר הרשמה.

  • Theory Seminar: Polynomial Protocols for Range Proofs

    דובר:
    אריאל גביזון (Aztec)
    תאריך:
    יום רביעי, 4.11.2020, 12:30
    מקום:
    Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code

    In a polynomial protocol a prover sends messages that are polynomials, and the verifier is allowed to check polynomial identities between these polynomials. The prover complexity is measured as the sum of degrees of the polynomials sent. The motivation for the definition is to capture prover complexity in zero knowledge proofs systems based on polynomial commitment schemes.

    We will present and illustrate this notion; and present an open question on improved protocols for “range proofs” – where given a committed polynomial f, and subset H of the field, we wish to prove f‘s values on H, are in a bounded domain [1,…,M].

    We will also attempt to give intuition as to why such range proofs are a crucial component in practical zero-knowledge systems.

    (Joint work with Zachary J. Williamson)

  • BebopNet: Deep Neural Models for Personalized Jazz Improvisations

    דובר:
    שונית חביב, הרצאה סמינריונית למגיסטר
    תאריך:
    יום רביעי, 11.11.2020, 12:00
    מקום:
    הרצאה באמצעות זום: https://technion.zoom.us/j99327852951
    מנחה:
    Prof. Ran El-Yaniv

    A major bottleneck in the evaluation of music generation is that music appreciation is a highly subjective matter. When considering an average appreciation as an evaluation metric, user studies can be helpful. The challenge of generating personalized content, however, has been examined only rarely in the literature. In this paper, we address generation of personalized music and propose a novel pipeline for music generation that learns and optimizes user-specific musical taste. We focus on the task of symbol-based, monophonic, harmony-constrained jazz improvisations. Our personalization pipeline begins with BebopNet, a music language model trained on a corpus of jazz improvisations by Bebop giants. BebopNet is able to generate improvisations based on any given chord progression. We then assemble a personalized dataset, labeled by a specific user, and train a user-specific metric that reflects this user's unique musical taste. Finally, we employ a personalized variant of beam-search with BebopNet to optimize the generated jazz improvisations for that user. We present an extensive empirical study in which we apply this pipeline to extract individual models as implicitly defined by several human listeners. Our approach enables an objective examination of subjective personalized models whose performance is quantifiable. The results indicate that it is possible to model and optimize personal jazz preferences and offer a foundation for future research in personalized generation of art. We also briefly discuss opportunities, challenges, and questions that arise from our work, including issues related to creativity.

  • Theory Seminar: Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations

    דובר:
    אריאל קוליק (מדעי המחשב, טכניון)
    תאריך:
    יום רביעי, 11.11.2020, 12:30
    מקום:
    Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code

    In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and 3-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random 1.5-approximation algorithm for Vertex Cover, whose running time of O*(1.01657k) substantially improves the best known running time of O*(1.0883k) [Brankovic and Fernau, 2013]. For 3-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of O*(1.0659k), improving the best known O*(1.29k) algorithm of [Brankovic and Fernau, 2012].

    The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations. We show an equivalence between these recurrences and a stochastic process, which we analyze using the Method of Types, by introducing an adaptation of Sanov’s theorem to our setting. We believe our novel analysis of recurrence relations, which is of independent interest, is a main contribution of this paper.