Skip to main content

ResearchHubLoading navigation…

Loading ResearchHub…

computational complexity - ResearchHub

Explore the network

Research, people, journals and institutions — all in one place.

Explore

01Research 02Smart search 03Researchers 04Journals 05Institutions 06RHR Rankings 07ResearchHub platform 08Events

Work together

Turn ideas into projects, questions and reusable datasets.

Connect

01Projects 02Questions 03Datasets

Stay informed

Follow trends, opportunities and your research library.

Insights

01Research trends 02Opportunities 03Library 04Research services 05ResearchHub Pro 06Pricing

ResearchHub

Explore ResearchHub.

Personal

01Recommended research 02Research intelligence

Home Search Network Library Log in

ResearchHub

Research, connected

Explore the graph

X

Download ResearchHub

GET IT ONGoogle PlayComing soonDownload on theApp StoreComing soonEXPLORE IT ONAppGalleryComing soon

Research

Research Researchers Journals Institutions RHR Rankings

Contribute

Projects Questions Datasets Opportunities

Platform

ResearchHub platform About Blog Community Help API Licensing

Shopping

Contact and support

Need help, have a question, or want to contact the ResearchHub team?

Contact and support support@aresearch.uk

© 2026 ResearchHub. Built for responsible scholarly connection.

Help Article feed Privacy Terms Cookies This work is licensed under Creative Commons Attribution 4.0 InternationalCC BY 4.0

Privacy-aware community infrastructure

Privacy & Cookies

We use cookies and similar technologies

ResearchHub uses necessary technologies for security, authentication and core functionality. Advertising choices, where available, are collected separately through Google's consent message.

See our Privacy Notice and Cookie Policy.

Journal

computational complexity

1016-3328 · Springer Science and Business Media LLC

101 verified public works

Browse all journals →

Fourier analysis for probabilistic communication complexity

1995 · 0 citations

Weakly complete problems are not rare

1995 · 0 citations

Super-logarithmic depth lower bounds via the direct sum in communication complexity

1995 · 0 citations

How can a complex square root be computed in an optimal way?

1995 · 0 citations

Pseudorandom generators and learning algorithms forAC 0

1995 · 0 citations

On closure properties of GapP

1994 · 0 citations

The hardness of approximation: Gap location

1994 · 0 citations

The power of adaptiveness and additional queries in random-self-reductions

1994 · 0 citations

Function-algebraic characterizations of log and polylog parallel time

1994 · 0 citations

Finding irreducible components of some real transcendental varieties

1994 · 0 citations

Invariance properties of RAMS and linear time

1994 · 0 citations

RL $$ \subseteq $$ SC

1994 · 0 citations

An algorithm to learn read-once threshold formulas, and transformations between learning models

1994 · 0 citations

A note on Rabin's width of a complete proof

1994 · 0 citations

Improving known solutions is hard

1993 · 0 citations

Bounds on tradeoffs between randomness and communication complexity

1993 · 0 citations

Relativized isomorphisms of NP-complete sets

1993 · 0 citations

Exponential lower bounds for the pigeonhole principle

1993 · 0 citations

On lower bounds for read-k-times branching programs

1993 · 0 citations

On the efficiency of effective Nullstellens�tze

1993 · 0 citations

Parallel pointer machines

1993 · 0 citations

Algorithmic aspects of Suslin's proof of Serre's conjecture

1993 · 0 citations

Non-deterministic exponential time has two-prover interactive protocols

1992 · 0 citations

Cartesian graph factorization at logarithmic cost per edge

1992 · 0 citations

Randomized range-maxima in nearly-constant parallel time

1992 · 0 citations

Graph isomorphism is low for PP

1992 · 0 citations

Majority gates vs. general weighted threshold gates

1992 · 0 citations

A new recursion-theoretic characterization of the polytime functions

1992 · 0 citations

Improved low-density subset sum algorithms

1992 · 0 citations

Counting connected components of a semialgebraic set in subexponential time

1992 · 0 citations

PreviousPage 3 of 4Next