BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1043
DTSTAMP:20230914T125948Z
SUMMARY:Ultra Large-scale Linear Programming based on Continuum Computing
DESCRIPTION:Speaker: Dr. Narendra Karmarkar (Former Homi Bhabha Chair Prof.
 \, TIFR)\n\nAbstract: \nAbstract: Ultra Large-scale Linear Programming re
 fers to class of problems where number of linear inequality constraints gr
 ows exponentially w.r.t. the number of variables. "Continuum Computing" is
  a generalization of powerful interior point algorithms\, and involves com
 puting with transcendental functions\, often in several complex variables.
  \n\nThere are many potential applications of this work to several practi
 cal problems-e.g. Explainable AI\, Topology optimization for 3D printing\,
  Optimal mask design for 7nm lithography etc. However\, our focus in this 
 seminar will be on core mathematical technique and it's parallelization on
  contemporary parallel machines.\n\nWe show that the "Potential function" 
 and it's first two derivatives\, involved in the algorithm for certain cla
 ss of ultra large scale LPs\, can be computed in polynomial time in the co
 ntinuum computing paradigm\, in spite of the fact that the feasible region
  is given by exponential number of constarints. Actual numerical cross-sim
 ulation on standard computing model and machines involves approximate nume
 rical computation of inverse Laplace transform. We also apply this approac
 h to establising non-satifiability of boolean formula\, which is known to 
 require exponentially long resolution-based proofs in the standard Turing 
 machine model. It is also believed that this task can not be done efficien
 tly in quantum computing model. Earlier exposition of this work from FOCM 
 can be found in Cornell Arxive 1412.3335.pdf\, and LNCS6457.\n
URL:https://www.tcs.tifr.res.in/web/events/1043
DTSTART;TZID=Asia/Kolkata:20200121T160000
DTEND;TZID=Asia/Kolkata:20200121T170000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR