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