https://cs.nyu.edu/dynamic/news/colloquium/1102/

Synopsis:

Standard (continuous or discrete) optimization problems t ypically assume that the dimension and the number of constrains in the pro blem are finite. In many practical situations\, either one or both of thes e two parameters may be infinite. Examples include: (i) the art gallery pr oblem from computational geometry\, where it is required to guard the infi nite set of points of an art gallery with the minimum number of cameras\, and (ii) robust optimization problems\, in which the coefficients of the c onstraints and/or the objective function are drawn from some infinite unce rtainty sets\, and the goal is to solve the optimization problem for the w orst case choice in each uncertainty set. In this talk\, we highlight some of these examples\, and then describe how the well-known multiplicative w eights update method can be applied to derive efficient approximation algo rithms for solving this type of problems.

END:VEVENT BEGIN:VEVENT UID:1101.event.events@cs.nyu.edu DTSTART:20181207T160000Z DTEND:20181207T170000Z DESCRIPTION:https://cs.nyu.edu/dynamic/news/colloquium/1101/\n\nSynopsis:\n \nThe goal of program synthesis is to allow programmers to specify the des ired computation in intuitive ways without having to write traditional cod e. The classical synthesis problem is to find a program that meets a corre ctness specification given as a logical formula. Recent work on synthesis and optimization illustrates many potential benefits of allowing the user to supplement the logical specification with a syntactic template that con strains the space of allowed implementations. The formulation of the synta x-guided synthesis problem (SyGuS) is aimed at standardizing the core comp utational problem common to these proposals in a logical framework. In thi s talk\, we first describe how a wide range of problems such as automatic synthesis of loop invariants\, program optimization\, program repair to de fend against timing-based attacks\, and learning programs from examples ca n be formalized as SyGuS instances. We then explain the counterexample-gui ded-inductive-synthesis strategy for solving the SyGuS problem\, its diffe rent instantiations\, and experimental evaluation over benchmarks from a v ariety of applications. We conclude by discussing how program synthesis an d machine learning can play mutually beneficial roles to transform the way we build software. DTSTAMP:20181207T160000Z LOCATION:60 Fifth Avenue\, 150 SUMMARY:Syntax-Guided Program Synthesis by Rajeev Alur URL:https://cs.nyu.edu/dynamic/news/colloquium/1101/ X-ALT-DESC;FMTTYPE=text/html:https://cs.nyu.edu/dynamic/news/colloquium/1101/

Synopsis:

The goal of program synthesis is to allow programmers to specify the desired computation in intuitive ways without having to write traditional code. The classical synthesis problem is to find a program tha t meets a correctness specification given as a logical formula. Recent wor k on synthesis and optimization illustrates many potential benefits of all owing the user to supplement the logical specification with a syntactic te mplate that constrains the space of allowed implementations. The formulati on of the syntax-guided synthesis problem (SyGuS) is aimed at standardizin g the core computational problem common to these proposals in a logical fr amework. In this talk\, we first describe how a wide range of problems suc h as automatic synthesis of loop invariants\, program optimization\, progr am repair to defend against timing-based attacks\, and learning programs f rom examples can be formalized as SyGuS instances. We then explain the cou nterexample-guided-inductive-synthesis strategy for solving the SyGuS prob lem\, its different instantiations\, and experimental evaluation over benc hmarks from a variety of applications. We conclude by discussing how progr am synthesis and machine learning can play mutually beneficial roles to tr ansform the way we build software.

END:VEVENT BEGIN:VEVENT UID:1100.event.events@cs.nyu.edu DTSTART:20181207T143000Z DTEND:20181207T153000Z DESCRIPTION:https://cs.nyu.edu/dynamic/news/colloquium/1100/\n\nSynopsis:\n \nThe New York Area Theory Day is a semi-annual conference\, aimed to brin g together people in the New York metropolitan area for one day of interac tion and discussion. The meeting is free and open to everyone\; in particu lar\, students are encouraged to attend.\nFor directions\, please see here .\nOrganizers:\n\nAlex Andoni\nYevgeniy Dodis\nKrzysztof Onak\n\nSome trav el support is provided by DIMACS/Simons Collaboration in Lower Bounds in C omputational Complexity through NSF grant #CCF-1836666.\nProgram\n\n\n\n9: 30 - 10:00\nCoffee and bagels\n\n\n10:00 - 10:55\n\nMike Saks (Rutgers)App roximating the Edit Distance to within a Constant Factor in Truly Subquadr atic Time\n\n\n\n10:55 - 11:15\nCoffee break\n\n\n11:15 - 12:10\n\nElad Ha zan (Princeton)Taking Control by Convex Optimization\n\n\n\n12:10 - 2:00\n Lunch Break\n\n\n2:00 - 2:55\n\nYael Tauman-Kalai (Microsoft Research New England)On Publicly Verifiable Non-Interactive Delegation Schemes from Sta ndard Assumptions\n\n\n\n2:55 - 3:15\nCoffee break\n\n\n3:15 - 4:10\n\nUrm ila Mahadev (UC Berkeley)Classical Verification of Quantum Computations\n\ n\n\n4:30 - 6:00\nFollow-up social\n\n\n\n \;\nSpeakers\n\nMike Saks ( Rutgers University)\nApproximating the Edit Distance to within a Constant Factor in Truly Subquadratic Time\nEdit distance is a widely used measure of similarity of two strings based on the minimum number of character inse rtions\, deletions\, and substitutions required to transform one string in to the other. The edit distance can be computed exactly using a classical dynamic programming algorithm that runs in quadratic time. No known algori thm improves on quadratic running time by more than a polylogarithmic fact or\, and Backurs and Indyk showed that a truly subquadratic time algorithm (running in time O(n^(2-a)) for some a>\;0) would violate the Strong Ex ponential Time Hypothesis (SETH).\nEven if we ask only for an algorithm th at approximates edit distance to within a constant factor\, no truly subqu adratic algorithm was known. In this talk I will describe recent work\, jo int with Diptarka Chakroborty\, Debarati Das\, Elazar Goldenberg\, and Mic hal Koucky giving such an algorithm.\n\nElad Hazan (Princeton University)\ nTaking Control by Convex Optimization\nLinear dynamical systems\, a.k.a. Kalman filtering\, are a class of time-series models widely used in roboti cs\, finance\, engineering\, and meteorology. In its general form (unknown system)\, learning LDS is a classic non-convex problem\, typically tackle d with heuristics like gradient descent ("backpropagation through time") o r the EM algorithm. I will present our new "spectral filtering" approach t o the identification and control of discrete-time general linear dynamical systems with multi-dimensional inputs\, outputs\, and a latent state. Thi s approach yields a simple and efficient algorithm for low-regret predicti on (i.e. asymptotically vanishing MSE) as well as finite-time control.\nBa sed on work with Karan Singh and Cyril Zhang\, and follow up works with Ho lden Lee\, Yi Zhang and Sanjeev Arora.\n\nYael Tauman-Kalai (Microsoft Res earch New England)\nOn Publicly Verifiable Non-Interactive Delegation Sche mes from Standard Assumptions\nIn this talk\, I will present new construct ions of publicly verifiable non-interactive delegation schemes\, under (po lynomial) falsifiable assumptions over bilinear groups. These schemes are in the common reference string (CRS) model\, where the CRS is long (polyno mial in the running time of the computation).\nThe first scheme is based o n a decisional assumption\, and supports any deterministic polynomial time computation. It is obtained by converting the delegation scheme of Kalai\ , Raz and Rothblum (STOC 2014) into a publicly verifiable one by construct ing a homomorphic encryption scheme with a weak zero-test\, a paradigm sug gested by Paneth and Rothblum (TCC 2017). The second scheme is based on a (constant size) search assumption\, but only supports log-space uniform ci rcuits of bounded depth. It is obtained by converting the interactive dele gation scheme of Goldwasser\, Kalai and Rothblum (J. ACM 2015) into a non- interactive one\, by replacing the sum-check protocol with a publicly veri fiable non-interactive one.\nPrior to this work\, publicly verifiable non- interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model)\, or under non-standard assumptions relat ed to obfuscation or multilinear maps.\nThis is joint work with Omer Panet h and Lisa Yang.\n\nUrmila Mahadev (UC Berkeley)\nClassical Verification o f Quantum Computations\nWe present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum compu tation. We achieve this by constructing a measurement protocol\, which all ows a classical string to serve as a commitment to a quantum state. The pr otocol forces the prover to behave as follows: the prover must construct a n n qubit state of his choice\, measure each qubit in the Hadamard or stan dard basis as directed by the verifier\, and report the measurement result s to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intra ctable for efficient quantum machines. This talk will not assume prior kno wledge of quantum computing or cryptography. DTSTAMP:20181207T143000Z LOCATION:Warren Weaver Hall\, 109 SUMMARY:New York Area Theory Day by IBM/NYU/Columbia URL:https://cs.nyu.edu/dynamic/news/colloquium/1100/ X-ALT-DESC;FMTTYPE=text/html:https://cs.nyu.edu/dynamic/news/colloquium/1100/

Synopsis:

The New York Area Theory Day is a semi-annual conference\ , aimed to bring together people in the New York metropolitan area for one day of interaction and discussion. The meeting is free and open to everyo ne\; in particular\, students are encouraged to attend.

\nFor direct ions\, please see here.

\nOrgani zers:

\n\nSome travel support is provid ed by DIMACS/Simons Collaboration in Lower Bounds in Computational Complex ity through NSF grant #CCF-1836666.

\n9:30 - 10:00 | Coffee and bagels |

10:00 - 10:55 | \n Mike Saks (Rutgers) |

10:55 - 11:15 | Coffee break |

11:15 - 12:10 | \n Elad Hazan (Princeton) |

12:10 - 2:00 | Lunch Break |

2:00 - 2:55 | \n Yael Tauman-Kalai (Microsoft Rese
arch New England) |

2:55 - 3:15< /td>\n | Coffee break |

3:15 - 4:10 | \n U
rmila Mahadev (UC Berkeley) |

4:30 - 6:00 | Follow-up social< /td>\n |

\;

\n\n

**Mike Saks** (Rutgers University)

*Approxima
ting the Edit Distance to within a Constant Factor in Truly Subquadratic T
ime*

Edit distance is a widely used measure of similarity of t wo strings based on the minimum number of character insertions\, deletions \, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a classical dynamic programmin g algorithm that runs in quadratic time. No known algorithm improves on qu adratic running time by more than a polylogarithmic factor\, and Backurs a nd Indyk showed that a truly subquadratic time algorithm (running in time O(n^(2-a)) for some a>\;0) would violate the Strong Exponential Time Hyp othesis (SETH).

\nEven if we ask only for an algorithm that approxim ates edit distance to within a constant factor\, no truly subquadratic alg orithm was known. In this talk I will describe recent work\, joint with Di ptarka Chakroborty\, Debarati Das\, Elazar Goldenberg\, and Michal Koucky giving such an algorithm.

\n\n

**Elad Hazan** (Pri
nceton University)

*Taking Control by Convex Optimization*<
/p>\n

Linear dynamical systems\, a.k.a. Kalman filtering\, are a class o f time-series models widely used in robotics\, finance\, engineering\, and meteorology. In its general form (unknown system)\, learning LDS is a cla ssic non-convex problem\, typically tackled with heuristics like gradient descent ("backpropagation through time") or the EM algorithm. I will prese nt our new "spectral filtering" approach to the identification and control of discrete-time general linear dynamical systems with multi-dimensional inputs\, outputs\, and a latent state. This approach yields a simple and e fficient algorithm for low-regret prediction (i.e. asymptotically vanishin g MSE) as well as finite-time control.

\nBased on work with Karan Si ngh and Cyril Zhang\, and follow up works with Holden Lee\, Yi Zhang and S anjeev Arora.

\n\n

**Yael Tauman-Kalai** (Microsof
t Research New England)

*On Publicly Verifiable Non-Interactive
Delegation Schemes from Standard Assumptions*

In this talk\, I will present new constructions of publicly verifiable non-interactive de legation schemes\, under (polynomial) falsifiable assumptions over bilinea r groups. These schemes are in the common reference string (CRS) model\, w here the CRS is long (polynomial in the running time of the computation).< /p>\n

The first scheme is based on a decisional assumption\, and support s any deterministic polynomial time computation. It is obtained by convert ing the delegation scheme of Kalai\, Raz and Rothblum (STOC 2014) into a p ublicly verifiable one by constructing a homomorphic encryption scheme wit h a weak zero-test\, a paradigm suggested by Paneth and Rothblum (TCC 2017 ). The second scheme is based on a (constant size) search assumption\, but only supports log-space uniform circuits of bounded depth. It is obtained by converting the interactive delegation scheme of Goldwasser\, Kalai and Rothblum (J. ACM 2015) into a non-interactive one\, by replacing the sum- check protocol with a publicly verifiable non-interactive one.

\nPri or to this work\, publicly verifiable non-interactive delegation schemes w ere only known under knowledge assumptions (or in the Random Oracle model) \, or under non-standard assumptions related to obfuscation or multilinear maps.

\nThis is joint work with Omer Paneth and Lisa Yang.

\n\n

**Urmila Mahadev** (UC Berkeley)

*Classica
l Verification of Quantum Computations*

We present the first p rotocol allowing a classical computer to interactively verify the result o f an efficient quantum computation. We achieve this by constructing a meas urement protocol\, which allows a classical string to serve as a commitmen t to a quantum state. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice\, measure each q ubit in the Hadamard or standard basis as directed by the verifier\, and r eport the measurement results to the verifier. The soundness of this proto col is enforced based on the assumption that the learning with errors prob lem is computationally intractable for efficient quantum machines. This ta lk will not assume prior knowledge of quantum computing or cryptography. END:VEVENT BEGIN:VEVENT UID:1098.event.events@cs.nyu.edu DTSTART:20181101T193000Z DTEND:20181101T203000Z DESCRIPTION:https://cs.nyu.edu/dynamic/news/colloquium/1098/\n\nSynopsis:\n \nIn this informal seminar\, Dr. Cabo will discuss an evolving program at Technical University Delft to improve learning in mathematics and mathemat ics-related subjects for a cohort of 12\,000 students.\nThe overall projec t goals are:\n\nAcademic success: to improve student performance in course s.\nTransfer: to enhance each student's ability to apply mathematics in en gineering contexts.\nEngagement: to increase student-participation in clas ses and student-motivation for learning.\n\nThe primary means to these end s include:\n\nBlended course flipping.\nCollaborative student interaction. \nContent reform.\nAutomation.\n\nIn addition\, Dr. Cabo would be pleased to learn about the ongoing activities at Courant. DTSTAMP:20181101T193000Z LOCATION:Warren Weaver Hall\, 317 SUMMARY:Innovative Teaching Seminar: Innovation in teaching mathematics: ob jectives\, methods\, and outcomes by Annoesjka Cabo URL:https://cs.nyu.edu/dynamic/news/colloquium/1098/ X-ALT-DESC;FMTTYPE=text/html:

https://cs.nyu.edu/dynamic/news/colloquium/1098/

Synopsis:

In this informal seminar\, Dr. Cabo will discuss an evolv ing program at Technical University Delft to improve learning in mathemati cs and mathematics-related subjects for a cohort of 12\,000 students.

\ nThe overall project goals are:

\n- \n
- Academic success: to imp rove student performance in courses. \n
- Transfer: to enhance each s tudent's ability to apply mathematics in engineering contexts. \n
- E ngagement: to increase student-participation in classes and student-motiva tion for learning. \n

The primary means to these ends include :

\n- \n
- Blended course flipping. \n
- Collaborative student interaction. \n
- Content reform. \n
- Automation. \n

In addition\, Dr. Cabo would be pleased to learn about the ongoing acti vities at Courant.

END:VEVENT BEGIN:VEVENT UID:1095.event.events@cs.nyu.edu DTSTART:20181019T150000Z DTEND:20181019T160000Z DESCRIPTION:https://cs.nyu.edu/dynamic/news/colloquium/1095/\n\nSynopsis:\n \nThrough a decades-long endeavor of building secure\, robust and performa nt systems\, we&rsquo\;ve developed a rich and deep understanding of centr alized computing models. However\, with recent advances in the area of blo ckchain\, a new decentralized model gives rise to even stronger security g uarantees. Cryptocurrencies and smart contracts are just two examples show casing the promises of the blockchain model of computation. Concurrently\, another fundamentally different approach to achieve stronger security is trusted execution environment (TEE)\, which has also seen a great advance recently with the debut of Intel SGX\, a CPU-based implementation of TEE.\ nHowever\, despite the nice features offered by TEE and blockchain\, neith er is ideal. The current blockchain systems suffer from serious practical limitations\, e.g. poor performance\, high energy consumption and lack of confidentiality. On the other hand\, TEE is imperfect in its specification and implementation\, and in isolation does not offer satisfactory availab ility guarantees. Motivated by these practical concerns\, my research focu ses on understanding the principles of a hybrid model that has the best of both worlds. In this talk\, I will talk about Town Crier and Ekiden\, two systems we built that demonstrate the benefits of synthesizing TEE and bl ockchains\, and the pitfalls arising from harmonizing them. DTSTAMP:20181019T150000Z LOCATION:60 Fifth Avenue\, 150 SUMMARY:Blockchains and Trusted Execution Environments: Towards a New Secur ity Paradigm by Fan Zhang URL:https://cs.nyu.edu/dynamic/news/colloquium/1095/ X-ALT-DESC;FMTTYPE=text/html:https://cs.nyu.edu/dynamic/news/colloquium/1095/

Synopsis:

Through a decades-long endeavor of building secure\, robu st and performant systems\, we&rsquo\;ve developed a rich and deep underst anding of centralized computing models. However\, with recent advances in the area of blockchain\, a new decentralized model gives rise to even stro nger security guarantees. Cryptocurrencies and smart contracts are just tw o examples showcasing the promises of the blockchain model of computation. Concurrently\, another fundamentally different approach to achieve strong er security is trusted execution environment (TEE)\, which has also seen a great advance recently with the debut of Intel SGX\, a CPU-based implemen tation of TEE.

\nHowever\, despite the nice features offered by TEE and blockchain\, neither is ideal. The current blockchain systems suffer f rom serious practical limitations\, e.g. poor performance\, high energy co nsumption and lack of confidentiality. On the other hand\, TEE is imperfec t in its specification and implementation\, and in isolation does not offe r satisfactory availability guarantees. Motivated by these practical conce rns\, my research focuses on understanding the principles of a hybrid mode l that has the best of both worlds. In this talk\, I will talk about Town Crier and Ekiden\, two systems we built that demonstrate the benefits of s ynthesizing TEE and blockchains\, and the pitfalls arising from harmonizin g them.

END:VEVENT X-WR-CALNAME:NYU CS Colloquia Calendar END:VCALENDAR