logo
ProjectForthcoming

Optimal Tradeoffs between Randomness, Time, and Space

Forthcoming · Israel

Source: EU Funding & Tenders Portal

Randomization is remarkably effective in algorithm design. In practice, randomized algorithms often outperform their deterministic counterparts; for example, there are randomized linear-time algorithms for problems where the best-known deterministic algorithms require exponential time. Yet, randomness is itself a computational resource, which may be scarce or costly. While some settings---such as

Status
Prospective
Sector
Power Generation (CCGT), Education
Location
Israel
Updated
19 Nov 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Optimal Tradeoffs between Randomness, Time, and Space

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

3 Q
The project “Optimal Tradeoffs between Randomness, Time, and Space” is an infrastructure initiative in the Power Generation (CCGT) sector, located in Israel. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Not available for this record.

Status

Original status

forthcoming

Taiyo status

Prospective

Taiyo last update

2026-11-19

Contact

Not available for this record.

Description

Description

Randomization is remarkably effective in algorithm design. In practice, randomized algorithms often outperform their deterministic counterparts; for example, there are randomized linear-time algorithms for problems where the best-known deterministic algorithms require exponential time. Yet, randomness is itself a computational resource, which may be scarce or costly. While some settings---such as cryptography---provably require randomness, in many others, notably time- and space-bounded computation, the situation is less clear. This raises the central question of when randomness is necessary or useful for efficient algorithms, and how to devise practical, generic recipes for efficient derandomization. In cases where randomness is indispensable, one typically requires access to purely random bits; however, natural sources of randomness are usually defective, making it a central goal to purify such crude randomness in a way suitable for applications. Understanding the power and limitations of derandomization is one of the biggest challenges in complexity theory, with deep connections to many other areas. This project tackles fundamental problems in derandomization and pseudorandomness, aiming to resolve the longstanding BPL vs. L problem, settling whether randomness is needed for space-efficient computation. It will also deepen the study of minimal-overhead derandomization, producing deterministic algorithms that match, up to negligible loss, the speed and memory footprint of their randomized counterparts. In parallel, it will develop the efficient use of weak randomness in algorithms and cryptographic protocols. A unifying theme across all goals is the design of new pseudorandomness primitives and the development of computational analogues of fundamental random-like mathematical structures. The project's outcomes are expected not only to push the frontiers of pseudorandomness but also to have a broad impact on other areas of computer science.

Location

Country

Israel

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Sector

Power Generation (CCGT), Education

Article published date

2026-09-01

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project