Search

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over any field other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0. We also observe that our super-polynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small-depth circuits using the known connection between algebraic hardness and randomness. [ABSTRACT FROM AUTHOR]

The paper discusses algorithmic priority inversion in mission-critical machine inference pipelines used in modern neural-network-based perception subsystems and describes a solution to mitigate its effect. In general, priority inversion occurs in computing systems when computations that are "less important" are performed together with or ahead of those that are "more important." Significant priority inversion occurs in existing machine inference pipelines when they do not differentiate between critical and less critical data. We describe a framework to resolve this problem and demonstrate that it improves a perception system's ability to react to critical inputs, while at the same time reducing platform cost. [ABSTRACT FROM AUTHOR]

This article details Charles Babbage’s theoretical computer program, the first attempt to specific how to mechanize complex algorithms with a computer, written in 1837. The article also discusses his theoretical computer, the Analytical Engine, that his program would have run on. Topics include Babbage’s first and second code tables and the design of the Analytical Engine.

The article discusses a research paper that applies online resource allocation algorithms to refugee resettlement, aiming to improve refugees' integration into local communities and employment prospects. By utilizing concepts from algorithm design, such as balancing resource utilization and maintaining capacity for future refugees, the authors were able to enhance the employability metric for resettlement agencies like the Hebrew Immigrant Aid Society (HIAS) by approximately 10%. This research not only addresses critical societal issues but also highlights the potential of algorithms to positively impact real-world outcomes for vulnerable populations, encouraging collaboration between algorithm designers and practitioners on important societal problems.

The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main component of popular lossless compression programs (such as bzip2) as well as recent powerful compressed indexes (such as the r-index7), central in modern bioinformatics. The compressibility of BWT is quantified by the number r of equal-letter runs in the output. Despite the practical significance of BWT, no nontrivial upper bound on r is known. By contrast, the sizes of nearly all other known compression methods have been shown to be either always within a polylog n factor (where n is the length of the text) from z, the size of Lempel--Ziv (LZ77) parsing of the text, or much larger in the worst case (by an nε factor for ε > 0). In this paper, we show that r = O (z log² n) holds for every text. This result has numerous implications for text indexing and data compression; in particular: (1) it proves that many results related to BWT automatically apply to methods based on LZ77, for example, it is possible to obtain functionality of the suffix tree in O (z polylog n) space; (2) it shows that many text processing tasks can be solved in the optimal time assuming the text is compressible using LZ77 by a sufficiently large polylog n factor; and (3) it implies the first nontrivial relation between the number of runs in the BWT of the text and of its reverse. In addition, we provide an O (z polylog n)-time algorithm converting the LZ77 parsing into the run-length compressed BWT. To achieve this, we develop several new data structures and techniques of independent interest. In particular, we define compressed string synchronizing sets (generalizing the recently introduced powerful technique of string synchronizing sets11) and show how to efficiently construct them. Next, we propose a new variant of wavelet trees for sequences of long strings, establish a nontrivial bound on their size, and describe efficient construction algorithms. Finally, we develop new indexes that can be constructed directly from the LZ77 parsing and efficiently support pattern matching queries on text substrings. [ABSTRACT FROM AUTHOR]

This article investigates artificial intelligence (AI) fairness in decision-making specifically examining the limitations of this process. The article discusses eight inherent limitations in AI fairness including lack of fairness in human decision-making used to train the AI model, lack of a universal fairness definition, and limited power over the complete decision-making process.

The article looks at how fairness can be defined and implemented in algorithmic decision-making. The author states that alternative, reasonable definitions of fairness can end up being mutually exclusive when operationalized in mathematical or algorithmic form. He discusses competing analyses of fairness in algorithms used to predict criminal behavior.

Recommender systems personalize content by recommending items to users. Item recommendation algorithms are evaluated by metrics that compare the positions of truly relevant items among the recommended items. To speed up the computation of metrics, recent work often uses sampled metrics where only a smaller set of random items and the relevant items are ranked. This paper investigates such sampled metrics in more detail and shows that they are inconsistent with their exact counterpart, in the sense that they do not persist relative statements, for example, recommender A is better than B, not even in expectation. Moreover, the smaller the sample size, the less difference there is between metrics, and for very small sample size, all metrics collapse to the AUC metric. We show that it is possible to improve the quality of the sampled metrics by applying a correction, obtained by minimizing different criteria. We conclude with an empirical evaluation of the naive sampled metrics and their corrected variants. To summarize, our work suggests that sampling should be avoided for metric calculation, however if an experimental study needs to sample, the proposed corrections can improve the quality of the estimate. [ABSTRACT FROM AUTHOR]

In this paper, we describe multi-itinerary optimization (MIO)--a novel Bing Maps service that automates the process of building itineraries for multiple agents while optimizing their routes to minimize travel time or distance. MIO can be used by organizations with a fleet of vehicles and drivers, mobile salesforce, or a team of personnel in the field, to maximize workforce efficiency. It supports a variety of constraints, such as service time windows, duration, priority, pickup and delivery dependencies, and vehicle capacity. MIO also considers traffic conditions between locations, resulting in algorithmic challenges at multiple levels (e.g., calculating time-dependent travel-time distance matrices at scale and scheduling services for multiple agents). To support an end-to-end cloud service with turnaround times of a few seconds, our algorithm design targets a sweet spot between accuracy and performance. Toward that end, we build a scalable approach based on the ALNS metaheuristic. Our experiments show that accounting for traffic significantly improves solution quality: MIO finds efficient routes that avoid late arrivals, whereas traffic-agnostic approaches result in a 15% increase in the combined travel time and the lateness of an arrival. Furthermore, our approach generates itineraries with substantially higher quality than a cutting-edge heuristic (LKH), with faster running times for large instances. [ABSTRACT FROM AUTHOR]

The article discusses an algorithm designed to compute maximum flow and minimum-cost flows. It builds on the works of prior researchers to propose new theorems and provides formulas and graphs to illustrate these theorems and schemes.

The article discusses Explainable artificial intelligence (XAI) and the expectation of artificial intelligence (AI) end users to understand how AI works, including how algorithmic decision making occurs. An overview of AI end users' desire for information on AI methodology on reaching decisions, including in regard to the ethical nature of AI, is provided.

The article focuses on how revisiting key algorithms from computing history can unlock the hidden efficiency in computer science problems. The author discusses the shortest-path problem that has been long-standing, explores the use of the Bellman-Ford algorithm, and examines the work of Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen.

This article explores the trends in computer science research in India from 2019 to 2022 based on research coming out of leading Indian technology institutes, including Chennai Mathematical Institute, Indian Institute of Science and Indian Institute of Technology Delhi. Topics include research on automata theory, formal verification, computational complexity research, and Algorithms research.

Exploring a potential way to immensely speed up algorithms for the group isomorphism problem. [ABSTRACT FROM AUTHOR]

Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSPs and the computation of the number of distinct elements in a data stream, also known as the zeroth frequency moment (F0) of a data stream. Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSPs and the computation of the number of distinct elements in a data stream, also known as the zeroth frequency moment (F0) of a data stream. [ABSTRACT FROM AUTHOR]

Flash-based solid-state drives (SSDs) are a key component in most computer systems, thanks to their ability to support parallel I/O at sub-millisecond latency and consistently high throughput. At the same time, due to the limitations of the flash media, they perform writes out-of-place, often incurring a high internal overhead which is referred to as write amplification. Minimizing this overhead has been the focus of numerous studies by the systems research community for more than two decades. The abundance of system-level optimizations for reducing SSD write amplification, which is typically based on experimental evaluation, stands in stark contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input and show that in this case, the greedy algorithm is optimal. Then, we design an online algorithm that uses predictions about the input. We show that when predictions are relatively accurate, our algorithm significantly improves over the greedy algorithm. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces. [ABSTRACT FROM AUTHOR]

This article discusses the use of theoretical analysis to measure the performance of algorithms and investigates its shortcomings using the field of sequencing bioinformatics. The author posits that theoretical analysis applied to algorithm performance has fallen short of its stated goals of predicting the empirical performance of an algorithm and being a yardstick to drive the design of new algorithms.

This article discusses the recent areas of focus at the National Institute of Informatics (NII) in Japan. First, a look at its academic services including SINET6, a backbone network service across Japan and its data platform service, the NII Research Data Cloud. The article also details NII research in computer science with projects in innovative computer vision and engineerable artificial intelligence, as well as applied research projects including a COVID-19 pneumonia diagnosis tool.

This article discusses how the combination of humans and artificial intelligence could target misinformation and polarization, by examining two scenarios- one where computing methods can assist human fact-checkers and one where human search methods can assist in search engine algorithms for personalization. Topics include the Australian Communication and Media Authority research on misinformation in Australia, whether filter bubbles are created by personalization attempts of algorithms, and the various computational methods that can assist fact-checking to prevent misinformation.

The author presents a set of puzzles involving tidy towers, a colored block stacking puzzle. First, several scenarios related to the puzzle are presented and solved. Lastly, the author presents two puzzles and information is provided for readers to submit their solutions.

The article addresses the topic of algorithm design in the solid-state drive (SSD) model of computation, noting its limitations as well as its benefits. The author references an accompanying paper which addresses one shortcoming in particular -- the phenomenon of "write amplification" -- by proposing a more accurate theoretical model of SSDs that incorporates read, write and erase operations.

The article explores generalization in deep learning algorithms and the role of implicit bias involved in training neural networks.

The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the small-set-flip decoding algorithm applied to the family of quantum expander codes. We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the bit-flip algorithm applied to the (classical) expander codes of Sipser and Spielman. [ABSTRACT FROM AUTHOR]

Memory leaks in web applications are pervasive and difficult to debug. Leaks degrade responsiveness by increasing garbage collection costs and can even lead to browser tab crashes. Previous leak detection approaches designed for conventional applications are ineffective in the browser environment. Tracking down leaks currently requires intensive manual effort by web developers, which is often unsuccessful. This paper introduces BLeak (Browser Leak debugger), the first system for automatically debugging memory leaks in web applications. BLeak’s algorithms leverage the observation that in modern web applications, users often repeatedly return to the same (approximate) visual state (e.g., the inbox view in Gmail). Sustained growth between round trips is a strong indicator of a memory leak. To use BLeak, a developer writes a short script (17–73 LOC on our benchmarks) to drive a web application in round trips to the same visual state. BLeak then automatically generates a list of leaks found along with their root causes, ranked by return on investment. Guided by BLeak, we identify and fix over 50 memory leaks in popular libraries and apps including Airbnb, AngularJS, Google Analytics, Google Maps SDK, and jQuery. BLeak’s median precision is 100%; fixing the leaks it identifies reduces heap growth by an average of 94%, saving from 0.5MB to 8MB per round trip. [ABSTRACT FROM AUTHOR]

This article details the concept of critical path tracing to analyze latency in complex distributed systems. Critical path tracing works by compiling a list of the steps responsible for the slowest path of request processing and then optimizing those steps to reduce latency overall. Topics include remote procedure call or RPC telemetry, central process unit of CPU profiler analysis, and distributed tracing analysis. A detailed look at how critical path tracing works is included.

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper, we study a number of flood-risk related problems: given a terrain Σ, represented as a triangulated xy-monotone surface with n vertices, a rain distribution, and a volume of rain ψ, determine which portions of Σ are flooded. We give an overview of efficient algorithms for these problems as well as explore the efficacy and efficiency of these algorithms on real terrains. [ABSTRACT FROM AUTHOR]

This article details the latest advances of the Shor algorithm and its impact on quantum computing. First, an explanation of Peter Shor’s algorithm developed in the mid-1990s is provided followed by a look at Oded Regev’s theoretical improvement, as well as Vinod Vaikuntanathan and Seyoon Ragavan’s contribution with a new scheme. Topics include modular multiplication, the quantum Fourier transform, and asymptotic performance.

This article discusses computational modeling and simulation, with a focus on the development of mathematical software with an emphasis on how it needs to grow in the future. Topics include the optimization necessary to both the mathematical models and algorithms that support computational science software development, with a focus on decreasing operations, packaging software, and performance portability.

The article discusses the development of the algorithm known as norms to address the statistic problem known as nearest neighbor, referencing papers in the "Annual Symposium on Foundations of Computer Science" and "Proceedings of the ACM Symposium on Theory of Computing" journals. An overview of researchers' designing of normed spaces is provided. The uses of data analysis and expander graphs, including in regard to measuring the distance from data points, are discussed.

The article focuses on the search for algorithms that can reduce the time needed for multiplication problems within the fields of machine learning (ML), deep learning (DL), and artificial intelligence (AI). Topics discussed include the history of matrix multiplication and the data science group DeepMind and their ML approach AlphaTensor.

This article presents information on how algorithms can be utilized to properly disperse natural disaster aid from governments and relief organizations. Topics include the need for automation and data analysis in order to assist in delivering aid in a timely and appropriate manner, how to prevent fraud in relief aid, and also how algorithms can make initial assessments for qualification of need in disaster situations. Organizations highlighted in the article include the American Red Cross, GiveDirectly, and the United Kingdom’s Department for Work & Pensions.

The article presents three principles concerning five challenges to the establishment of trustworthy artificial intelligence (AI), including the development computer languages and algorithms for data modeling, trustworthy-by-construction design, and complex machine learning (ML) representations.

The article describes several achievements in the field of theoretical computer science (TCS) and computer research in Latin America. It discusses several areas of research that were developed by regional conferences including LATIN, LAGOS, and Latincrypt. The article discusses research including graph theory, pattern matching and information retrieval, and algorithms.

The article discusses the relationship between model counting and streaming algorithms, and it mentions the differences between the idea of efficiency for model counting and the idea of estimating the amount of distinct elements in a given data stream. Data streams and a hashing-based technique for model counting are assessed, as well as a Satisfiability problem.

The article offers the author's comments on the role of experimental evidence in computer science research. According to the author, sorting algorithms were a major issue for computer scientists in the 1960s. He adds that experiments conducted on specialized data should not be accepted under any circumstances.

The article examines trust in artificially intelligent (AI) systems as well as their regulation by various governments including those of the European Union, U.S., and China. The author predicates trust in AI on its perceived safety and reliability and calls for the continued human oversight of AI systems ("human-in-the-loop" or "society-in-the-loop"). Applications of artificial intelligence are outlined including military strategy, law enforcement, and healthcare.

This article details the evaluation process for post-quantum cryptography conducted by the United States National Institute of Standards and Technology, NIST. Post-quantum cryptography would combat the use of quantum computing to crack public keys used for encryption. The NIST began this process by first seeking public-key protocols and algorithms for digital signatures from the public and now have four finalists with several backup candidates, they will evaluate all and release results in 2024. Topics include the first component of the evaluation, classical attack vulnerability, and the difficulties in assessing the second component, quantum attack vulnerability.

The article provides a perspective on the use of algorithms in maintaining maximum flow through computing networks. Offers a critique of various max-flow theorems and algorithms. Discusses prior research into max-flow applications. Mentions the hope for future breakthroughs in developing scalable max-flow algorithms.

COMPUTATIONAL THINKING, WHICH centers around devising abstractions for problems so they can be solved with computational steps and efficient algorithms, is a concept that serves not only computer science (CS) but progressively more of science and everyday life. [ABSTRACT FROM AUTHOR]

The article utilizes the adaptive learning computer system AlphaZero in order to examine how variations of the game of chess would proceed at what is referred to as a superhuman level. According to the article, AlphaZero marks a significant milestone in the field of artificial intelligence (AI) and the use of algorithms in computer chess.

The article discusses the concept of topic novelty and its impact upon accuracy in the news and journalism, and whether artificial intelligence (AI) algorithms can counter fake news. The article discusses AI, accuracy, and fake news during the COVID-19 pandemic and an experiment performed on Amazon Mechanical Turk (AMT).

We present a method that achieves state-of-the-art results for synthesizing novel views of complex scenes by optimizing an underlying continuous volumetric scene function using a sparse set of input views. Our algorithm represents a scene using a fully connected (nonconvolutional) deep network, whose input is a single continuous 5D coordinate (spatial location (x, y, z) and viewing direction (θ, φ)) and whose output is the volume density and view-dependent emitted radiance at that spatial location. We synthesize views by querying 5D coordinates along camera rays and use classic volume rendering techniques to project the output colors and densities into an image. Because volume rendering is naturally differentiable, the only input required to optimize our representation is a set of images with known camera poses. We describe how to effectively optimize neural radiance fields to render photorealistic novel views of scenes with complicated geometry and appearance, and demonstrate results that outperform prior work on neural rendering and view synthesis. [ABSTRACT FROM AUTHOR]

The article describes static program analysis in computer programming and code. According to the article, static program analysis is comprised of algorithms that have the ability to take facts from the source code of another computer program in the everyday process of software development. The article draws a distinction between the terms pass and tool, the implementation of static analysis tools, and the significance of human behavior in the adoption of static tools.

Surface tension is an important property of liquids. It has diverse uses such as testing water contamination, measuring alcohol concentration in drinks, and identifying the presence of protein in urine to detect the onset of kidney failure. Today, measurements of surface tension are done in a lab environment using costly instruments, making it hard to leverage this property in ubiquitous applications. In contrast, we show how to measure surface tension using only a smartphone. We introduce a new algorithm that uses the small waves on the liquid surface as a series of lenses that focus light and generate a characteristic pattern. We then use the phone camera to capture this pattern and measure the surface tension. Our approach is simple, accurate, and available to anyone with a smartphone. Empirical evaluations show that our mobile app can detect water contamination and measure alcohol concentration. Furthermore, it can track protein concentration in the urine, providing an initial at-home test for proteinuria, a dangerous complication that can lead to kidney failure. [ABSTRACT FROM AUTHOR]

The authors present their thoughts concerning the research sphere of algorithms with predictions, particularly focusing upon a research trend in machine learning (ML) predictors in order to go beyond the concept of the worst-case analysis.

The article discusses the development and relative effectiveness of anti-surveillance cosmetic makeup designed to elude facial-recognition technology. It also examines the rapid pace of computer vision development, facial-detection algorithms, and how law enforcement agencies utilize facial recognition systems.

Commonsense reasoning remains a major challenge in AI, and yet, recent progresses on benchmarks may seem to suggest otherwise. In particular, the recent neural language models have reported above 90% accuracy on the Winograd Schema Challenge (WSC),22 a commonsense benchmark originally designed to be unsolvable for statistical models that rely simply on word associations. This raises an important question--whether these models have truly acquired robust commonsense capabilities or they rely on spurious biases in the dataset that lead to an overestimation of the true capabilities of machine commonsense. To investigate this question, we introduce WinoGrande, a large-scale dataset of 44k problems, inspired by the original WSC, but adjusted to improve both the scale and the hardness of the dataset. The key steps of the dataset construction consist of (1) large-scale crowdsourcing, followed by (2) systematic bias reduction using a novel AfLite algorithm that generalizes human-detectable word associations to machine-detectable embedding associations. Our experiments demonstrate that state-of-the-art models achieve considerably lower accuracy (59.4%-79.1%) on WinoGrande compared to humans (94%), confirming that the high performance on the original WSC was inflated by spurious biases in the dataset. Furthermore, we report new state-of-the-art results on five related benchmarks with emphasis on their dual implications. On the one hand, they demonstrate the effectiveness of WinoGrande when used as a resource for transfer learning. On the other hand, the high performance on all these benchmarks suggests the extent to which spurious biases are prevalent in all such datasets, which motivates further research on algorithmic bias reduction. [ABSTRACT FROM AUTHOR]

ROBOT CAPABILITIES ARE maturing across domains, from self-driving cars to bipeds to drones. As a result, robots will soon no longer be confined to safetycontrolled industrial settings; instead, they will directly interact with the general public. The growing field of human-robot interaction (HRI) studies various aspects of this scenario, from social norms to collaborative manipulation to human-robot teaming, and more. Researchers in HRI have made great strides in developing models, methods, and algorithms for robots acting with and around humans. [ABSTRACT FROM AUTHOR]

THERE IS A new technology on the horizon that will forever change the information security and privacy industry landscape. Quantum computing, together with quantum communication, will have many beneficial applications but will also be capable of breaking many of today's most popular cryptographic techniques that help ensure data protection--in particular, confidentiality and integrity of sensitive information. These techniques are ubiquitously embedded in today's digital fabric and implemented by many industries such as finance, health care, utilities, and the broader information communication technology (ICT) community. It is therefore imperative for ICT executives to prepare for the transition from quantum-vulnerable to quantum-resistant technologies. [ABSTRACT FROM AUTHOR]

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model, but even when their assumptions are violated. Unfortunately, in high dimensions, being provably robust and being efficiently computable are often at odds with each other. We give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian that is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute or could tolerate only an inverse-polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, but also it turns out to be highly practical in a variety of settings. [ABSTRACT FROM AUTHOR]