Lower bounds for recognizing small cliques on CRCW PRAM's
type: Item
instance of: scholarly article
title: Lower bounds for recognizing small cliques on CRCW PRAM's
zbMATH Open document ID: 0707.68032
DOI: 10.1016/0166-218X(90)90079-R
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4162258
zbMATH Keywords: lower bounds
zbMATH Keywords: cliques
zbMATH Keywords: models of computation
zbMATH Keywords: CRCW PRAM
zbMATH Keywords: fan-in circuits
zbMATH Keywords: constant-depth circuits
author: Paul Beame
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: First-order definability on finite structures
cites work: Limits on the power of concurrent-write parallel machines
cites work: Optimal bounds for decision problems on the CRCW PRAM
cites work: Q3682518
cites work: Q4065548
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q4728251
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Simulation of Parallel Random Access Machines by Circuits
full work available at URL: 0166-218x(90)90079-r
OpenAlex ID: W2152034968
description: scientific article; zbMATH DE number 4162258