I am a Ph.D. student in the Computer Science Department at the Technion, Israel. My research, advised by Prof. Benny Kimelfeld in the Technion Data & Knowledge Laboratory, focuses on theoretical aspects of database query optimization. I love teaching, mainly competitive programming and combinatorics. I also enjoy participating in improvisational theater and swing dancing.
Contact. snofca at cs.technion.ac.il
The complexity of listing query answers over a database depends on the query structure. However, a query with a naturally difficult structure can sometimes be adjusted into an easy form by using additional information. My work aims at identifying how fast we can solve any given query. This is done either by providing an efficient algorithm for answering the query or by proving that an algorithm with a given complexity cannot be achieved.
When can we answer queries in a uniformly random order with linear preprocessing and polylogarithmic delay? We propose an algorithm for random permutation that relies on random access to the query answers, and we inspect when conjunctive queries and unions of conjunctive queries admit efficient algorithms for these two tasks.
Published as "Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration".Arxiv PODS 20 Slides
Which unions of conjunctive queries can be answered with constant delay following linear preprocessing? A union of tractable CQs is always tractable. We show that some unions containing intractable CQs are, in fact, tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. We prove that for several classes of queries, free-connexity fully captures the tractable UCQs.
PODS 2019 Best Student Paper. Published as "Enumeration Complexity of Unions of Conjunctive Queries".
Invited for a special issue of ACM Transaction on Database Systems (TODS) on selected publications from PODS 2019.
A known dichotomy identifies which conjunctive queries can be answered with constant delay following linear preprocessing. What happens in the common case the database exhibits dependencies among attributes? Some queries classified as hard are in fact tractable if dependencies are accounted for. We generalize the dichotomy to accommodate functional dependencies and cardinality dependencies.
Published as "Enumeration Complexity of Conjunctive Queries with Functional Dependencies".
Invited for a special issue of Theory of Computing Systems (TOCS) on selected publications from ICDT 2018.
Tree decompositions can be used to optimize join queries, but finding the best decomposition is NP-hard. We present an algorithm that enumerates all the proper tree decompositions (or minimal triangulations) of a graph in incremental polynomial time. This can be used as an anytime algorithm to improve on any method for finding a single tree decomposition (or triangulation).
Published as "Efficiently Enumerating Minimal Triangulations".Arxiv PODS 17 DAM 20 Code Talk
Classes I taught.
Combinatorics. This is the first class I taught, two years into my undergraduate studies, and my favorite "standard" class to teach. For me, the satisfaction in teaching comes from showing students how to think more effectively, and I enjoy the type of thinking that is at the core of this class. This class is taken by up to 350 students in normal semesters and 50 students in summer semesters. I received the Permanent Excellent Faculty Instructor Award for teaching this class in spring 2015 and winter 2016.
Competitive Programming. Workshop in Competitive Programming is a very unique class where students gain experience solving problems quickly in teams of three using short programs. The problems sometimes require ad-hoc solutions, sometimes use known paradigms (such as dynamic programming, divide and conquer, clever complete search, or a greedy approach), and sometimes incorporate known algorithms involving graphs, strings, maths, computational geometry, or any topic that can be considered computer science. Teamwork is also a big component of this class as each team of three students works together on one computer to try to solve up to 10 problems in 5 hours. To this aim, it is important to identify bottlenecks, prioritize the work, and communicate effectively with the other teammates. This is where students often get hands-on experience with topics they had only learned theoretically before. A competition at the end of the semester determines which team represents the Technion in the following Southwestern Europe Regional Contest (SWERC) of the International Collegiate Programming Contest (ACM-ICPC). I took this class myself as a student, and this was undoubtedly the best class of my degree! My team then competed in SWERC 2014 in Porto. As a TA, I pushed for expanding this class significantly to equip the students with the tools and tips we gained with experience. We added an hour of teaching prior to the weekly two-hour practices, and built lessons covering what we thought are the most useful parts in each of the aspects mentioned above.
Based on a website template by w3.css