Monthly CIRC Symposia
Every third Friday of the month, the Center for Integrated Research Computing hosts a research symposium (known as the CIRC Symposium), where faculty, staff, and student researchers convene to learn about research projects utilizing the center’s resources, meet potential collaborators, and learn about new technologies and trends in research computing. This event is user-driven and features presentations by researchers using CIRC systems. CIRC Symposia are open to all members of the university community and a complimentary lunch is provided.
The Center for Integrated Research Computing (CIRC) hosted a symposium on Friday, November 18th from 12 p.m. to 1 p.m. EDT in Wegmans 1400 and over Zoom. The featured speaker was Venkatesan Guruswami from the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Please see the title and abstract below
When and Why Do Efficient Algorithms Exist (For Constraint Satisfaction and Beyond)?
Venkatesan Guruswami, PhD
Department of Electrical Engineering and Computer Sciences University of California, Berkeley
Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems, the (recently proved) algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. Inspired and emboldened by this, one might speculate a polymorphic principle in more general contexts, with symmetries in the solution space being the genesis of efficient algorithms. Beginning with some background on constraint satisfaction problems (CSP) and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP” where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring and discrepancy minimization). We will also point out some of the many challenges that remain, and touch upon connections to fine-grained complexity and optimization.
VENKATESAN GURUSWAMI is a Professor of Computer Science and Mathematics at UC Berkeley and a senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor’s degree from IIT Madras, and his Ph.D. from MIT. Venkat’s research interests lie in theoretical computer science and related mathematics and include error-correcting codes, approximate optimization, and computational complexity. He is currently the Editor-in-Chief of the Journal of the ACM. Venkat was a co-winner of the 2012 Presburger Award, and his other honors include a Simons Investigator award, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and an IEEE Information Theory Society Paper Award. He is a fellow of the ACM and the IEEE.
Co-Sponsored by the Department of Computer Science and the Center for Integrated Research Computing (CIRC) Joint Talk for the Computer Science Colloquium Series and CIRC Symposium
Information about previous CIRC Symposia is available.
CIRC Summer School
Every summer, CIRC hosts a four-week training session on various operating systems, programming languages, computational programs and libraries, and data analytics tools for the research community. Known as the “CIRC Summer School,” these workshops are broken down into individual topics and feature small, interactive, classroom-based instruction sessions. Topics range from basic training in Linux to optimizing codes for parallel computing. The courses are designed for beginner and advanced users alike. Extra emphasis is placed on using the various available languages, libraries, etc., specifically on BlueHive.
Check again soon for an announcement about the next Summer School!
CIRC Winter Boot Camp
Have you ever wanted to learn how to program or add a new programming language to your existing knowledge? Have you been looking for the right time to pick up a few essential technical computing skills to help with your research projects or course work? Well, now you have the opportunity during the CIRC Winter Boot Camp!
The Center for Integrated Research Computing (CIRC) hosts a multi-week winter program to help students, postdocs, research staff, and faculty learn new programming languages and sharpen their computing and data analytics skills. The classes are designed for beginners and cover basic topics to give enough direction to move on to self-learning tutorials or other more advanced coursework.
Check again soon for an announcement about the next Winter Boot Camp!
The Center for Integrated Research Computing (CIRC) offers workshops every Spring and Fall that introduce users to the BlueHive computing environment and other computing resources that CIRC supports. The workshops include sessions in the morning targeted for new and beginning users, and afternoon sessions covering a few more in-depth topics and tools and applications that are available to the research community.
If you would like more information, please contact CIRC or follow the link below.
Annual CIRC Poster Session
The Center for Integrated Research Computing holds the Annual CIRC Poster Session at the end of each Spring semester. At this event, attendees discover the wide range of research that is enabled by computation and displayed to the University community. This event provides an informal venue to share computational and data analytics techniques and methodologies with colleagues from a wide variety of disciplines.
Check again later for an announcement about the next CIRC Poster Session!