Dani Dorfman, Simon Döring, Martin G. Herold et al.
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs?If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for graph problems called algorithms with isomorphic…
Isaac Rudich, Louis-Martin Rousseau
Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with…Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3).
A mathematical proof shows that existing algorithms achieve the best possible tradeoff between computer memory, passes over data, and solution quality.A mathematical proof shows that existing algorithms achieve the best possible tradeoff between computer memory, passes over data, and solution quality.
Joshua A. Grochow, Gábor Ivanyos, Youming Qiao et al.
The finite group isomorphism problem asks whether two finite groups of order N are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in…The finite group isomorphism problem asks whether two finite groups of order N are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time N^(log N + O(1)).
Slobodan Mitrović, Theodore Pan
We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph G on n…We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph G on n vertices to a graph with n · poly log n edges while…
Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and 2-edge connectivity of a graph with worst-case polylogarithmic update time.We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and 2-edge connectivity of a graph with worst-case polylogarithmic update time.
Yiannis Giannakopoulos, Johannes Hahn
We study the classical multi-item monopoly setting with a single additive buyer and m heterogeneous items whose values are independent but not necessarily identically…We study the classical multi-item monopoly setting with a single additive buyer and m heterogeneous items whose values are independent but not necessarily identically distributed.
Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya
Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory.Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code…
Adrian Wurm
Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its…Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its training data, whether a fault in its stored parameters can…
Yang Cai, Vineet Gupta, Yanchen Jiang et al.
Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives–such as maximizing total value subject…Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives–such as maximizing total value subject to a return-on-spend (ROS) constraint–rather than manual…
Oliver Korten
We prove that Parity requires 2^n^(Ω(1)) size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95].We prove that Parity requires 2^n^(Ω(1)) size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95].
Victor Lecomte, Prasanna Ramakrishnan
Four decades on, H{aa}stad's classical 2^Ω(n^(1/(d-1))) lower bound for depth-d circuits computing Parity remains the best known AC⁰ circuit lower bound for any explicit…Four decades on, H{aa}stad's classical 2^Ω(n^(1/(d-1))) lower bound for depth-d circuits computing Parity remains the best known AC⁰ circuit lower bound for any explicit function.