BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1362
DTSTAMP:20231130T091202Z
SUMMARY:Exploring Size Complexity in Decision Trees
DESCRIPTION:Speaker: Yogesh Dahiya (IMSc Chennai)\n\nAbstract: \nDecision t
 rees are one of the simplest and most basic models  of computation. Given
  a computational task\, in the decision tree  model(query model) of compu
 tation\, the task is computed by adaptively  querying the input while str
 iving to minimize the number of queries  required. While the model is sim
 ple\, it still remains a puzzle with  many unresolved questions. Many sig
 nificant breakthroughs in recent  years have been intricately tied to exp
 loring various facets of the  query model. Discovery of new connections b
 etween proof complexity and  query complexity and the development of quer
 y-to-communication lifting  theorems have played a pivotal role in gettin
 g new results in proof  complexity\, boolean circuit complexity\, and com
 munication complexity.  In the decision tree model\, there are two natura
 l complexity measures  of importance: the depth complexity (the worst-cas
 e number of queries  asked by a query algorithm) and the size complexity 
 (the space  required to store the query algorithm). While significant att
 ention  has been devoted to the former\, the latter remains relatively  
 under-explored.In this talk\, we will investigate the relationship between
  size  complexity and other complexity measures\, and understand the  ad
 vantages that randomness offers in the context of size complexity.  When 
 the computation task is a search problem\, a nuanced usage of  randomness
  by Gat and Goldwasser (ECCC-11) led to the beautiful notion  of pseudo-d
 eterministic mode of computation. Pseudo-deterministic  algorithms are ra
 ndomized algorithms that solve search problems by  almost always providin
 g the same canonical solution (per each input).  They aim to address the 
 inherent variability observed in randomized  algorithms\, which often pro
 duce different correct results across  multiple runs. We will explore the
  interplay between determinism\,  randomness\, and pseudo-determinism con
 cerning size complexity in the  decision tree model. Additionally\, we wi
 ll discuss more generalized  variants of decision trees\, where queries a
 re allowed to be functions  from specific classes rather than ordinary si
 ngle-variable queries.\n
URL:https://www.tcs.tifr.res.in/web/events/1362
DTSTART;TZID=Asia/Kolkata:20231201T160000
DTEND;TZID=Asia/Kolkata:20231201T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR