Lower bounds for recognizing small cliques on CRCW PRAM's

DOI10.1016/0166-218X(90)90079-RzbMath0707.68032OpenAlexW2152034968MaRDI QIDQ919820

P. W. Beame

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90079-r

zbMATH Keywords

lower boundscliquesconstant-depth circuitsmodels of computationCRCW PRAMfan-in circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Unnamed Item ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Exponential lower bounds for the pigeonhole principle ⋮ Unnamed Item ⋮ Ehrenfeucht-Fraïssé Games on Random Structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Limits on the power of concurrent-write parallel machines
• First-order definability on finite structures
• Simulation of Parallel Random Access Machines by Circuits
• Parity, circuits, and the polynomial-time hierarchy
• Optimal bounds for decision problems on the CRCW PRAM

This page was built for publication: Lower bounds for recognizing small cliques on CRCW PRAM's