BEGIN:VCALENDAR

VERSION:2.0

PRODID:-//wp-events-plugin.com//7.4.2//EN

TZID:Asia/Jerusalem

X-WR-TIMEZONE:Asia/Jerusalem
BEGIN:VEVENT

UID:361@math.technion.ac.il

DTSTART;TZID=Asia/Jerusalem:20250101T143000

DTEND;TZID=Asia/Jerusalem:20250101T152000

DTSTAMP:20250109T093842Z

URL:https://math.technion.ac.il/events/omri-ben-eliezer/

SUMMARY:Omri Ben-Eliezer (Technion) -- On the instance optimality of detect
 ing collisions and subgraphs
DESCRIPTION:Lecturer:Omri Ben-Eliezer\n Location:814 Amado\n Suppose you ar
 e given query access to a function f: [n] -&gt\; [n] and would like to fin
 d\, say\, a collision or a fixed point in f. Does knowing the "structure" 
 of the function help with this task? (Here\, by "knowing the structure" we
  mean that the algorithm is given\, in addition\, an unlabeled copy of the
  function f.) What about subgraph detection problems in graphs? Does knowi
 ng the structure of a graph G help\, say\, in finding triangles?\n\n\n\nTh
 e answer\, as it turns out\, strongly depends on the object we wish to fin
 d. There are three distinct classes of behavior. For some very simple obje
 cts\, an algorithm that knows nothing about the input can actually be O(1)
 -competitive with one "knowing the structure" for all inputs. In most prob
 lems\, including fixed point detection and triangle finding\, the gap can 
 be as large as polynomial in n. But most interestingly\, there are two pro
 blems that seem to be "almost instance optimal": collision detection in fu
 nctions and claw (3-star) detection in graphs. We conjecture both properti
 es are Theta(log n)-optimal\, prove the lower bound\, and provide initial 
 evidence toward a proof of a matching upper bound.\n\n\n\nJoint work with 
 Tomer Grossman and Moni Naor.\n\n&nbsp\;\n\n&nbsp\;\n 
CATEGORIES:Combinatorics Seminar,Seminars
LOCATION:814 Amado

END:VEVENT

BEGIN:VTIMEZONE

TZID:Asia/Jerusalem

X-LIC-LOCATION:Asia/Jerusalem

BEGIN:STANDARD

DTSTART:20241027T010000

TZOFFSETFROM:+0300

TZOFFSETTO:+0200

TZNAME:IST

END:STANDARD

END:VTIMEZONE
END:VCALENDAR