Hillar C.J.,Mathematical science Research Institute |
Lim L.-H.,University of Chicago
Journal of the ACM | Year: 2013
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-, and VNP-hard. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra General Terms: Algorithms, Theory Additional Key Words and Phrases: Numerical multilinear algebra, tensor rank, tensor eigenvalue, tensor singular value, tensor spectral norm, system of multilinear equations, hyperdeterminants, symmetric tensors, nonnegative definite tensors, bivariate matrix polynomials, NP-hardness, #P-hardness, VNP-hardness, undecidability, polynomial time approximation schemes. © 2013 ACM.
Leach J.,Mathematical science Research Institute
Classical and Quantum Gravity | Year: 2016
We prove the existence of a large class of initial data for the vacuum Einstein equations which possess a finite number of asymptotically Euclidean and asymptotically conformally cylindrical or periodic ends. Aside from being asymptotically constant, only mild conditions on the mean curvature of these initial data sets are imposed. © 2016 IOP Publishing Ltd.
Agency: NSF | Branch: Continuing grant | Program: | Phase: | Award Amount: 4.51M | Year: 2015
Through its scientific activities, the Mathematical Sciences Research Institute (MSRI) of Berkeley, California, seeks to strengthen U.S. research in the mathematical sciences. MSRI works to develop innovative mathematical programs and organizes and hosts a variety of working groups for mathematical scientists. At any given time during the academic year, MSRI is home to leading researchers, postdoctoral fellows, and graduate students, who come from around the country and the world in order to participate in semester-long research programs on topics drawn from a broad spectrum of active areas in fundamental mathematics. Programs catalyze new research collaborations and create connections for U.S. mathematicians with leading researchers from around the world. In addition, MSRI organizes and hosts many workshops each year that benefit the mathematics community at large; subjects include mathematics education, recent breakthroughs in various areas of the mathematical sciences, and graduate and undergraduate training and research. As a result of these combined activities, approximately 2,000 mathematical scientists each year visit MSRI lectures. MSRI actively promotes the diversity of the research population in the mathematical sciences. Through public events and other outreach programs, the Institute also contributes to the publics understanding of mathematics and its utility in modern society, as well as appreciation of the inherent beauty of mathematics.
Long-term programs are organized around subjects proposed by members of the mathematics research community that are then developed with the advice and guidance of MSRIs Scientific Advisory Committee. Programs involve a wide range of areas in mathematics, from number theory to subjects connected to physics and computation. The Institute works to combine fields and pair programs in ways that are often novel, lead to new connections, and sometimes lead to the recognition of a new field. Each program features introductory and research workshops, a Connections for Women workshop, seminars and lectures, postdoctoral mentoring, and collaborative research among the participants, with the goal of assimilating and expounding the latest results in the area, stimulating new research and collaborations, and disseminating the results, through traditional publication channels as well as video streaming. Two-week Summer Graduate Schools introduce ideas and trends in mathematics that broaden students perspective and introduce them to future colleagues. Other programs include Hot Topics Workshops, planned at short range, which complement the long-term programs and their workshops, catalyzing research progress in rapidly developing fields in the mathematical sciences.
Agency: NSF | Branch: Standard Grant | Program: | Phase: | Award Amount: 48.21K | Year: 2013
Although programs such as PBSs NOVA and NPRs Science Friday and magazine articles in Scientific American and Discovery make the sciences accessible to the public, content about mathematics and mathematicians is scarce. Taking the Long View presents a unique opportunity to learn about the extraordinary mathematical contributions of Shiing-shen Chern. Going beyond an exposition of his foundational contributions to differential geometry, the film interweaves 20th century Chinese history to ground Cherns intellectual and cultural accomplishments. The result is a startling realization of Cherns far-reaching impact on the development of pure mathematics, specifically, differential geometry, and on cross-cultural mathematical collaboration. For its analysis of how historical events shaped the life of an extraordinary man who greatly advanced pure mathematics and mathematical exchange between China and the West, Taking the Long View is unlike anything else currently available, especially given its focus on Chinese and Western relations. This 54-minute film has been released as a DVD with 35 minutes of extra features that explain, among other things, the Gauss-Bonnet Theorem and Cherns insightful proof, Cartans technique of moving frames for treating geometric problems, vector bundles and Cherns discovery of their topological classes, and other mathematical topics. This project will make the film available for broadcast on more than 300 local public television stations through syndication by the National Educational Telecommunications Association (NETA). Following its broadcast, it will be made available for online streaming from several web sites.
Taking the Long View is a unique and valuable contribution to the goal of bringing mathematics to nonmathematical audiences. Syndication of Taking the Long View by NETA will expose an extremely large and diverse audience (the general public) to accessible mathematical concepts, Shiing-shen Cherns dedication to and impact on mathematics, and the importance of Western and Chinese relations in the development of mathematics. Viewers will learn about fundamental concepts in differential geometry, such as Chern classes; Cherns critical role in disseminating Cartans innovative techniques (often described as moving frames); and Cherns great success in promoting cross-cultural mathematical collaboration by encouraging Chinese and Western mathematicians to study and teach abroad. The films focus on the impact of Chinese and Western relations on the development of mathematics distinguishes the film from other programs and articles about mathematics. Furthermore, Shiing-shen Chern remains an original and highly respected thinker within the field whose contributions cannot be overestimated.
Agency: NSF | Branch: Standard Grant | Program: | Phase: INFRASTRUCTURE PROGRAM | Award Amount: 50.00K | Year: 2016
This project involves the preparation of a documentary film about mathematician Yitang Zhang for national broadcast on public television via American Public Television syndication (APT) in May, June of 2017. Counting from Infinity: Yitang Zhang and the Twin Prime Conjecture premiered theatrically in January 2016. It tells the story of Yitang Zhang, who made an important breakthrough towards solving the Twin Prime Conjecture in 2013. In the film, the story of Zhangs quiet perseverance amidst adversity, and his preference for thinking and working in solitude, is interwoven with a history of the Twin Prime Conjecture as told by several mathematicians, many of whom have wrestled with this enormously challenging problem in Number Theory - Daniel Goldston, Kannan Soundararajan, Andrew Granville, Peter Sarnak, Enrico Bombieri, James Maynard, Nicholas Katz, David Eisenbud, Ken Ribet, and Terry Tao. The film was produced and directed by George Csicsery, and has proven highly effective at conveying mathematical ideas to the general public through the human stories of the mathematicians behind the ideas.
Modification of the film in preparation for public television broadcast involves editing, adding required modules, closed captioning, and other technical work, as well as promotional efforts aimed at individual station programmers.
Agency: NSF | Branch: Continuing grant | Program: | Phase: | Award Amount: 300.00K | Year: 2015
Macaulay2 is a free computer algebra software system dedicated to the qualitative investigation of systems of polynomial equations in many variables. The computations it can perform have uses in many fields of mathematics and science, from algebraic geometry to genomics. The research to be done under this grant extends the computational methods built into Macaulay2. The project will enable new collaborations between Macaulay2 software developers from the research community and scientists from physics and biology as well as pure mathematicians. Experimental results found with Macaulay2 have helped in the formulation, development, and solution of many conjectures. Through the improvement of computational tools, the proposed research will impact many fields of mathematics and science.
The project has two main aspects. First, it addresses the infrastructure of symbolic computation as a research tool supported by Macaulay2. This includes the implementation of new features, bug fixes, user support, further documentation, and multiplatform releases of new versions that will maintain and develop Macaulay2 as a major tool used for research in a broad range of fields. Secondly, research done under this project will develop better algorithms for some key computational problems, such as computing the cohomological and topological invariants of algebraic varieties, and will develop applications to string theory, supersymmetry, and discrete models of biological networks.
Agency: NSF | Branch: Standard Grant | Program: | Phase: | Award Amount: 674.67K | Year: 2010
The project has three main aspects. First, it addresses the infrastructure of symbolic computation as a research tool supported by Macaulay2. This includes the implementation of new features, bug fixes, user support, further documentation, and multiplatform releases of new versions that will maintain and develop Macaulay2 as a major tool used for research in a broad range of fields. Second, it addresses manpower needs, by training young people in the use of Macaulay2, and by engaging and expanding the collaborations that have been a hallmark of Macaulay2 development. In this way it will enable more of the research community to develop competence in this kind of experimental mathematics. Third, research done under this project will develop better algorithms for some key computational problems, such as computing normalization. Other goals of the research are to improve the implementation of the core Groebner basis algorithms, uncover new methods for the study of biological networks, and develop better and more reliable methods in the emerging field of numerical algebraic geometry.
Macaulay2 is a free computer algebra software system dedicated to the qualitative investigation of systems of polynomial equations in many variables. The computations it can perform have uses in many fields of mathematics and science, from algebraic geometry to genomics. The research to be done under this grant extends the computational methods built into Macaulay2. In addition, the grant will provide many opportunities to train young mathematicians and other scientists in the use of these tools, and to bring other experts? knowledge to bear on them through conferences, schools, and Intense Collaboration Workshops centered on the important issues in this field. The project will enable new collaborations between Macaulay2 software developers from the research community and scientists from physics and biology as well as pure mathematicians. It will introduce graduate students, postdocs, and junior and senior mathematicians to the use of computers in research mathematics and help them acquire powerful skills in programming and development of algorithms that will enhance their own research. Experimental results found with Macaulay2 have helped in the formulation, development, and solution of many conjectures. Through the improvement of computational tools, the proposed research will impact many fields of mathematics and science.
Agency: NSF | Branch: Standard Grant | Program: | Phase: OFFICE OF MULTIDISCIPLINARY AC | Award Amount: 93.22K | Year: 2015
The meeting Partnerships: Workshop on Non-profit/NSF Collaborations will take place at the National Science Foundation on May 28-29, 2015. The National Science Foundation (NSF) and non-profit organizations each provide critical support to the U.S. basic research enterprise in the mathematical and physical sciences. While the missions of these funders differ, many of their goals align and the grantee communities have significant overlap. In recent years, efforts of private organizations have played a more and more significant part of the whole picture of the funding of science. There are great opportunities: private support can be very flexible and allow discovery-driven investigation beyond what public funding can tolerate. This workshop will explore the ways in which the Directorate of Mathematical and Physical Sciences at the NSF and private foundations can form useful partnerships.
This workshop will examine partnerships between the Directorate of Mathematical and Physical Sciences (MPS) at NSF and non-profit funders in MPS-related disciplines to
- understand different models of collaboration (the how);
- understand different motivations for collaboration (the why); and
- develop opportunities for future communication and/or collaboration.
After examining partnerships of various types, participants will discuss creative opportunities for future coordination. Discussions will entail both scientific focus and logistical considerations. The central events of the workshop will be a series of case studies, and a series of small-group discussions with reports back to the workshop as a whole. A technical writer will take notes and synthesize take-away themes for a report that will be made widely available.
Agency: NSF | Branch: Standard Grant | Program: | Phase: DISCOVERY RESEARCH K-12 | Award Amount: 99.04K | Year: 2015
Improving mathematics education in the US will require the commitment and input of many professionals, including research mathematicians. Engaging research mathematicians in mathematics education requires supporting productive participation of mathematicians by fostering an understanding of critical issues in mathematics education and the capacity for working across professional communities. The conferences will be designed and implemented by one of the premiere mathematics institutes positioned to continue its example of substantial and disciplined engagement of mathematicians with mathematics educators toward the improvement of mathematics education. The design of the conferences will allow the mathematics and mathematics education community to address issues that are vital to the improvement of mathematics education in the US, with a focus on engaging mathematicians systematically in this work. A special emphasis will be on engaging department chairs and other leaders in the mathematical community in this work to broaden the impact of the work. These conferences will continue and build upon prior successful strategies with new innovations for engaging the mathematics community to increase the awareness and activity of mathematicians to make productive contributions to mathematics education, working across professional communities, to be active stewards of the field. The Discovery Research K-12 program (DRK-12) seeks to significantly enhance the learning and teaching of science, technology, engineering and mathematics (STEM) by preK-12 students and teachers, through research and development of innovative resources, models and tools (RMTs). Projects in the DRK-12 program build on fundamental research in STEM education and prior research and development efforts that provide theoretical and empirical justification for proposed projects.
The goals of the two workshops are to recruit key individuals in the mathematics and mathematics education research communities to work together for the improvement of mathematics education; frame critical issues; draw attention to issues of diverse participation and success in mathematics; and provide images of productive engagement for participants to draw upon as they return to their professional communities. The design of the conferences is based on a program logic model that the recruitment and productive engagement of mathematicians and mathematics departments in critical issues of mathematics education nationally will increase our understanding of how to involve mathematicians in education work in a systematic, informed, and salable way, and will lead to more mathematicians constructively supporting mathematics education. The conferences, held in 2015 and 2016, will focus on developmental mathematics and other critical issues in mathematics education. An internationally renowned Education Advisory Committee (EAC) will charge a group of lead organizers to refine a set of guiding questions that will provide coherence for the planning, selection of speakers, and activities. A cross-section of mathematicians and mathematics educators, including those representing leadership and teams in both communities, will be invited to participate. The lead organizers will finalize a plan of action developed in consultation with the conference participants and EAC, to be disseminated online and to serve as a focus of the conference reports. The conferences would be rigorously evaluated to inform the organizers and the broader community on whether innovations in the conference design support increased mathematicians involvement and study the hypothesized sources of impact via survey and interviews with mathematicians and other participants.
Agency: NSF | Branch: Continuing grant | Program: | Phase: WORKFORCE IN THE MATHEMAT SCI | Award Amount: 587.83K | Year: 2012
The MSRI Undergraduate Program (MSRI-UP) is designed to provide the opportunity as well as the long-term support and mentorship that talented undergraduate students need in order to have access to research careers in science and mathematics. Each year, 18 students will participate in an intense six-week summer research experience where they will work in teams to complete a research project. The students will be led by a research director, a post-doc and two graduate student assistants. Students will also make a final presentation at MSRI. The topics for the summer program are of current mathematical interest and importance, and represent part of faculty research leaders research program. These include areas of combinatorics, finite geometry and computational algebra.
MSRI-UP aims to increase the number of students from underrepresented groups in the mathematical sciences Ph.D. programs. The primary objective is to identify students with an interest in mathematics, and provide necessary experiences, tools, information and long-term support for them to have a viable option to pursue a graduate education in the mathematical sciences. In addition to the research component, the students will attend a series of professional development workshops and colloquia, including graduate school program information. After the summer, students will present their work in poster sessions at national conferences such as the Joint Mathematics Meetings and the annual meeting of the Society for Advancement of Chicanos and Native Americans in Science (SACNAS).