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

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

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

• ### Pixel Club: Hinge-Minimax Learner for the Intersection of K-hyperplanes

דובר:
מרגריטה אוסדצ'י (אונ' חיפה)
תאריך:
יום שלישי, 1.12.2015, 11:30
מקום:
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל

In this work we consider non-linear classifiers that positively classify a point when it resides in the intersection of $k$ hyperplanes. We learn these classifiers by minimizing the minimax risk of the negative training examples and the sum of hinge-loss of the positive training examples. These classifiers fit typical real-life datasets that consist of a small number of positive data points and a large number of negative data points. Such approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, which is used in a single constraint on the minimax risk, as opposed to SVM, in which the number of variables is equal to the size of the training set. We also provide empirical risk bounds and show that they are dimensionally independent and decay as $1/\sqrt{m}$ for $m$ samples.

We propose an efficient algorithm for training an intersection of finite number of hyperplanes and we demonstrate the effectiveness of our classifiers on real data, including letter and scene recognition. We show that these classifiers are significantly faster than kernel methods, as they only calculate $k$ inner products. In contrast, kernel SVMs produce a significant number of support vectors rendering the classification impractical.

• ### Applications of Dimensionality Reduction Techniques in Genetics

דובר:
Eran Halperin - COLLOQUIUM LECTURE - Note unusual hour
תאריך:
יום שלישי, 1.12.2015, 15:00
מקום:
חדר 337-8 טאוב.
קישור:
http://www.cs.technion.ac.il/~colloq/20151201_15_00_Halperin.html
• ### Theory Seminar: An Instance of Subset Sum Hard for Cutting Planes (An Invitation to Proof Complexity)

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

Proof complexity started its life as an attempt to prove that NP is different from coNP.

The main goal of the area is to show that no proof system can prove that all negative instances of 3SAT are unsatisfiable using polynomial size proofs.

However, this goal has proved too difficult, and nowadays the area concentrates on proving the same for specific proof systems.

The focus of this talk is the proof system *cutting planes*, which is the proof complexity analog of the popular branch-and-bound algorithm for integer programming. A proof in this system consists of a sequence of inequalities over Boolean variables. We will describe a pair of such inequalities (encoding an unsatisfiable subset sum instance) that have no common Boolean solutions, but proving this in cutting planes requires a proof of exponential size.

No familiarity with proof complexity will be assumed.

Joint work with Pavel Hrubes and Massimo Lauria.

• ### CGGC Seminar: Introduction to Constraint System Decomposition

דובר:
בוריס סוסין (מדעי המחשב, טכניון
תאריך:
יום ראשון, 6.12.2015, 13:30
מקום:
חדר 337, בניין טאוב למדעי המחשב

I this talk, we will introduce the concept of constraint system decomposition and show how it is beneficial for solving problems in computational geometry. We will also present the geometric and algebraic approaches to constraint decomposition and discuss their advantages and disadvantages with respect to each other.

• ### CGGC M.Sc. Seminar: Piecewise Linear Tangent Vector Fields on Triangulated Surfaces

דובר:
אלכסנדר ג'רבטיאן (מדעי המחשב, טכניון)
תאריך:
יום ראשון, 13.12.2015, 13:30
מקום:
חדר 337, בניין טאוב למדעי המחשב

Tangent vector field processing on discrete surfaces poses many challenges, one of the first being the choice of representation. The popular choice of piecewise-constant vector fields per face leads to very simple expressions and algorithms, at the price of lower accuracy and difficulties in defining derivatives and smoothness energies. Piecewise-linear vector fields on vertices lead to better results, but also to a much higher complexity due to the use of curved triangles, making important differential operators challenging to compute. We propose a very simple, yet powerful, edge-based discrete representation of tangent vector fields, which can be trivially generalized to represent N-RoSy fields. Our representation is as simple as the face-based representation (allowing to easily compute operators such as divergence and curl), yet has accuracy comparable to vertex-based representations. We demonstrate applications of this representation to tangent vector field design under a variety of constraints.

This talk summarizes the M.Sc. research of the speaker under the supervision of Prof. Miri Ben-Chen.

• ### When Can Limited Randomness Be Used in Repeated Games?

דובר:
Moni Naor - COLLOQUIUM LECTURE
תאריך:
יום שלישי, 15.12.2015, 14:30
מקום:
חדר 337-8 טאוב.
קישור:
http://www.cs.technion.ac.il/~colloq/20151215_14_30_Naor.html