96 citations · 442 across the 64 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 4 cited
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen
We study regular expression membership testing: Given a regular expression of size and a string of size , decide whether the string is in the language described by the regul…
cs.DS2016★ 1 cited
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Karl Bringmann
Given a set of positive integers and a target value , the Subset Sum problem asks whether any subset of sums to . A textbook pseudopolynomial time algorithm by Be…
cs.DM2016★ 23 cited
Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
Karl Bringmann, Ralph Keusch, Johannes Lengler
In Chung-Lu random graphs, a classic model for real-world networks, each vertex is equipped with a weight drawn from a power-law distribution, and two vertices form an edge indepen…