09/01/2021 - According to UTCS Professor Dana Moshkovitz, randomized algorithms are sometimes faster than the best known deterministic algorithms—this is known to be true in the field of computer science. But her research group’s work proves that they can be quadratically faster, under plausible complexity assumptions. Under complexity assumptions, the upper bound on this is tight and problems exist for which randomization gives a quadratic speedup. Read more
Subscribe to Topic: Dean Doron