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

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

  • ceClub: Dr. Philip M. Merlin Memorial Lecture and Prize Award: Scheduling Algorithms for the 4G Cellular Networks

    דובר:
    ראובן כהן (מדעי המחשב, טכניון)
    תאריך:
    יום רביעי, 23.5.2012, 11:30
    מקום:
    חדר 1003, בניין מאייר, הפקולטה להנדסת חשמל

    Cellular networks are becoming more and more crucial to our daily lives and operators are seeking new technologies for increasing their bandwidth. Examples for such technologies are cell sectorization, fractional frequency reuse, and coordinated multipoint Tx/Rx. To take advantage of these new technologies, the scheduler logic at the base station needs to determine not only when to transmit each packet but also what modulation and coding scheme to use, which frequency reuse area's resources, and by which transmitting antenna. In this talk, I will discuss all these modern scheduling problems and present algorithms for solving them

  • Theory Seminar: Optimal Testing of Multivariate Polynomials over Small Prime Field

    דובר:
    אלעד הרמתי (מדעי המחשב, טכניון)
    תאריך:
    יום רביעי, 23.5.2012, 12:30
    מקום:
    טאוב 201

    We consider the problem of testing if a given function f is close to a n-variate degree d polynomial over the finite field of q elements. The natural, low-query, test for this property would be to pick the smallest dimension t= t(q,d )≈ d/q such that every function of degree greater than d reveals this feature on some t-dimensional affine subspace and to test that f when restricted to a random t-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only qt queries, independent of n. Previous works, by Alon et al., and Kaufman and Ron and Jutla et al. , showed that this natural test rejected functions that were Ω(1)-far from degree d-polynomials with probability at least Ω(q−t) (the results of hold for all fields, while the results of hold only for fields of prime order). Thus to get a constant probability of detecting functions that were at constant distance from the space of degree d polynomials, the tests made q^{2t} queries. Kaufman and Ron also noted that when q is prime, then q^t queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. It was unclear if the soundness analysis of these tests were tight and this question relates closely to the task of understanding the behavior of the Gowers Norm. This motivated the work of Bhattacharyya et al., who gave an optimal analysis for the case of the binary field and showed that the natural test actually rejects functions that were Ω(1)-far from degree d-polynomials with probability at least Ω(1).

    In this work we give an optimal analysis of this test for all fields showing that the natural test does indeed reject functions that are Ω(1)-far from degree d polynomials with Ω(1)-probability. Our analysis thus shows that this test is optimal (matches known lower bounds) when q is prime. Our approach extends the proof technique of Bhattacharyya et al., however it has to overcome many technical barriers in the process. The natural extension of their analysis leads to an O(q^d) query complexity, which is worse than that of Kaufman and Ron for all q except 2! The main technical ingredient in our work is a tight analysis of the number of “hyperplanes” (affine subspaces of co-dimension 1) on which the restriction of a degree dpolynomial has degree less than d. We show that the number of such hyperplanes is at most O(qtq,d ) — which is tight to within constant factors.

    Joint work with Amir Shpilka and Madhu Sudan.

  • Computing in the 21st Century: The Georgia Tech Model

    דובר:
    Zvi Galil
    תאריך:
    יום שלישי, 29.5.2012, 14:30
    מקום:
    חדר 337-8 טאוב.
    קישור:
    http://www.cs.technion.ac.il/~colloq/20120529_14_30_Galil.html

  • Theory Seminar: From Irreducible Representations to Locally Decodable Codes

    דובר:
    עופר ניימן (אונ' בן-גוריון)
    תאריך:
    יום רביעי, 30.5.2012, 12:30
    מקום:
    טאוב 201

  • Coverage-Driven Refinement of Conceptual Representations

    דובר:
    חגי טולידנו, הרצאה סמינריונית למגיסטר
    תאריך:
    יום רביעי, 30.5.2012, 13:30
    מקום:
    טאוב 601
    מנחה:
    Assoc. Prof. Shaul Markovitch

    Many text processing tasks are based on estimating semantic relatedness between texts. For example, in information retrieval, relevancy of documents can be determined based on the semantic distance from the query. Recently, many algorithms have been developed for evaluating semantic relatedness based on a conceptual representation of the input texts. The concept spaces for these algorithms are based, in most cases, on large repositories of knowledge, such as Wikipedia and Wordnet. These large concept spaces often yield representations that consist of very large collections of concepts, that in many cases have a negative impact on the performance of the semantic tasks due to redundancy that gives a superficially large weight to less relevant concepts, thus hiding important semantic aspects of the texts. In this work we present a new algorithm for conceptual representations that are based on hierarchical concept spaces. The algorithm incrementally adds strongly-associated concepts to the representation, while using the hierarchical structure of the semantic database to maximize coverage. We test the new algorithm for text relatedness tasks and show its advantage over existing approaches.

  • Safe Zones: An Efficient Approach to Distributed Monitoring

    דובר:
    אמיר עבוד, הרצאה סמינריונית למגיסטר
    תאריך:
    יום רביעי, 30.5.2012, 16:30
    מקום:
    טאוב 601
    מנחה:
    Prof. A. Schuster and Prof. D. Keren

    Many monitoring tasks over distributed data streams can be formulated as a continuous query using a function that is defined over the global average of data vectors derived from the streams. The query will typically produce an alert when the value of the function crosses a predefined threshold. A fundamental problem in efficient scalable implementation of such threshold queries is that the data streams are distributed, sometimes over a wide geographical region. Moving all the data to a centralized data center for query processing may incur infeasible communication overheads and inflated data center resource costs. In some cases it may be prohibited altogether by the sheer aggregated size of the data, or by privacy laws. The goal is thus to enhance scalability by processing the query locally, using as little communication and global coordination as possible. We present a novel scheme for communication reduction in distributed monitoring using local constraints. Communication and global coordination are required only in the event that the local constraints are violated by the incoming data. Our work improves on previous work in a few critical aspects. First, whereas previous work required constructing a ``distributed cover'' of the entire convex hull of the local data vectors, our work compiles constraints that are designed to cover only the global average; further, they are directly matched and tailored to fit the local data distribution at each stream. The result is a dramatic decrease in the required volume of communication compared to previous state of the art, up to two orders of magnitude in our experiments with real-life data. Both the experiments and theoretical study suggest that the improvement factor increases with the dimension of the data. Also, in contrast to previous work, which necessitated complicated constraints and required enormous computational effort over each of the streams, our scheme can use very simple constraints which incur negligible local overhead. This latter advantage makes our new approach applicable to thin, battery-operated sensors and cellular devices.

  • CGGC Seminar: On the possibility of simple parallel computing of Voronoi diagrams and Delaunay Graphs

    דובר:
    דניאל רים (ברזיל)
    תאריך:
    יום ראשון, 3.6.2012, 13:00
    מקום:
    חדר 337, בניין טאוב למדעי המחשב

    Although many algorithms for computing Euclidean Voronoi diagrams of point sites have been published, most of them are sequential in nature and hence cast inherent difficulties on the possibility to compute the diagrams in parallel. We present a new algorithm which enables the (combinatorial) computation of each of the Voronoi cells independently of the other ones. The algorithm is significantly different from previous ones and some of the ideas related to it are in the spirit of convex analysis.

    A new combinatorial structure for representing the cells is described along the way, and the computation of the corresponding Delaunay graph follows as a simple consequence.

    An implementation of the algorithm (done by Omri Azencot) will be presented.

  • The surprises of Quick Sort

    דובר:
    Micha Hofri
    תאריך:
    יום שלישי, 5.6.2012, 14:30
    מקום:
    חדר 337-8 טאוב.
    קישור:
    http://www.cs.technion.ac.il/~colloq/20120605_14_30_Hofri.html

  • ceClub: Improved Bounds for Byzantine Self-Stabilizing Clock Synchronization

    דובר:
    כריסטוף לנזן (מכון ויצמן למדע)
    תאריך:
    יום רביעי, 13.6.2012, 11:30
    מקום:
    חדר 337, בניין טאוב למדעי המחשב

    The challenging task of Byzantine self-stabilizing pulse synchronization requires that, in the presence of a minority of nodes that are permanently maliciously faulty, the non-faulty nodes must start firing synchronized pulses in a regular fashion after a finite amount of time, regardless of the initial state of the system. We study this problem under full connectivity in a model where nodes have local clocks of unknown, but bounded drift, and messages are delayed for an unknown, but bounded time.

    We present a generic scheme that, given a synchronous consensus protocol P, defines a self-stabilizing pulse synchronization algorithm A(P). If P terminates within R rounds (deterministically or with high probability), A(P) stabilizes within O(R) time (deterministically or with high probability, respectively). Utilizing different consensus routines, our transformation yields various improvements over previous techniques in terms of stabilization time and bit complexity. Finally, we sketch how to establish the abstraction of synchronous, integer-labeled rounds on top of pulse synchronization, at essentially the same complexity bounds.

    We will discuss our approach and its merits assuming no previous knowledge on the problem, however, basic familiarity with consensus will be beneficial.

  • Principles of Reasoning with Graphical Models

    דובר:
    Rina Dechter
    תאריך:
    יום שלישי, 19.6.2012, 14:30
    מקום:
    חדר 337-8 טאוב.
    קישור:
    http://www.cs.technion.ac.il/~colloq/20120619_14_30_Dechter.html