skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: SIGACT News Complexity Theory Column 108
Warmest thanks to Rafael Pass and Muthu Venkitasubramaniam for this issue's guest column, "Average-Case Complexity Through the Lens of Interactive Puzzles." When I mentioned to them that my introduction would have a section on Alan Selman's passing, they immediately wrote back that they were very sorry to hear of Alan's passing, and mentioned (as you will see discussed in the second page of their article), "The main problem that we are addressing actually goes back to a paper of Even, Selman, and Yacobi from 1984: "The Complexity of Promise Problems with Applications to Public-Key Cryptography'." It is beautiful, and a tribute to the lasting influence of Alan's research, that in the 2020s his work from many decades earlier is helping shape the field's dialogue.  more » « less
Award ID(s):
2006496
PAR ID:
10249208
Author(s) / Creator(s):
Date Published:
Journal Name:
ACM SIGACT News
Volume:
52
Issue:
1
ISSN:
0163-5700
Page Range / eLocation ID:
41 to 46
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. That the school-to-work transition can be challenging for many recent engineering graduates is well known [1]–[7]. However, current students and faculty rarely get an opportunity to learn directly from the mistakes, regrets, and hindsight of recent graduates during their first few years in the workplace. In order to help make students’ transition to engineering practice easier, and, relatedly, to help faculty prepare them in salient ways, this paper addresses the following research questions: 1) What do newcomer civil engineers believe are the biggest mistakes they made in their first few years on the job? and 2) If they could go back to when they began their jobs, what would they have done differently? As part of a mixed-methods, longitudinal study that aims to explore organizational socialization in engineering practice, sixteen early career civil engineers who worked in different firms around the country were asked about their work experiences, including their biggest mistakes and what they would have done differently at work knowing what they know now. Participants said their biggest mistakes related to not asking enough questions, undervaluing/not advocating for oneself, and staying in a position they dislike. Less mentioned issues included specific personal habits, attitudes, and unrealistic expectations from university education. When asked what they would have done differently from the first day at work until now, most responses related to having more confidence, networking and socializing more, and other specific personal behaviors, such as better organization. Less mentioned themes included requesting a higher salary, asking more questions, learning more material, and advocating for their own interests. The results have important implications for successfully preparing civil engineering students to begin their careers. By identifying these gaps in preparation, the paper points to recommendations for the civil engineering community. 
    more » « less
  2. The Consultative Committee for Space Data Systems (CCSDS) 141.11-O-1 Line Product Code (LPC) provides a rare opportunity to compare maximum-likelihood decoding and message passing. The LPC considered in this paper is intended to serve as the inner code in conjunction with a (255,239) Reed Solomon (RS) code whose symbols are bytes of data. This paper represents the 141.11-O-1 LPC as a bipartite graph and uses that graph to formulate both maximum likelihood (ML) and message passing algorithms. ML decoding must, of course, have the best frame error rate (FER) performance. However, a fixed point implementation of a Neural-Normalized MinSum (N-NMS) message passing decoder closely approaches ML performance with a significantly lower complexity. 
    more » « less
  3. The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity. 
    more » « less
  4. Just-in-Time (JIT) compilers are ubiquitous in modern computing systems and are used in a wide variety of software. Dynamic code generation bugs, where the JIT compiler silently emits incorrect code, can result in exploitable vulnerabilities. They, therefore, pose serious security concerns and make quick mitigation essential. However, due to the size and complexity of JIT compilers, quickly locating and fixing bugs is often challenging. In addition, the unique characteristics of JIT compilers make existing bug localization approaches inapplicable. Therefore, this paper proposes a new approach to automatic bug localization, explicitly targeting the JIT compiler back-end. The approach is based on explicitly modeling architecture-independent back-end representation and architecture-specific code-generation. Experiments using a prototype implementation on a widely used JIT compiler (Turbofan) indicate that it can successfully localize dynamic code generation bugs in the back-end with high accuracy. 
    more » « less
  5. null (Ed.)
    Airlines have introduced a back-to-front boarding process in response to the COVID-19 pandemic. It is motivated by the desire to reduce passengers' likelihood of passing close to seated passengers when they take their seats. However, our prior work on the risk of Ebola spread in aeroplanes suggested that the driving force for increased exposure to infection transmission risk is the clustering of passengers while waiting for others to stow their luggage and take their seats. In this work, we examine whether the new boarding processes lead to increased or decreased risk of infection spread. We also study the reasons behind the risk differences associated with different boarding processes. We accomplish this by simulating the new boarding processes using pedestrian dynamics and compare them against alternatives. Our results show that back-to-front boarding roughly doubles the infection exposure compared with random boarding. It also increases exposure by around 50% compared to a typical boarding process prior to the outbreak of COVID-19. While keeping middle seats empty yields a substantial reduction in exposure, our results show that the different boarding processes have similar relative strengths in this case as with middle seats occupied. We show that the increased exposure arises from the proximity between passengers moving in the aisle and while seated. Such exposure can be reduced significantly by prohibiting the use of overhead bins to stow luggage. Our results suggest that the new boarding procedures increase the risk of exposure to COVID-19 compared with prior ones and are substantially worse than a random boarding process. 
    more » « less