A Logical Characterization of Constant-Depth Circuits over the Reals

Research output: Chapter in book/report/conference proceedingConference contributionResearchpeer review

View graph of relations

Details

Original languageEnglish
Title of host publicationLogic, Language, Information, and Computation
Subtitle of host publication27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings
EditorsAlexandra Silva, Renata Wassermann, Ruy de Queiroz
Pages16-30
Number of pages15
Volumeabs/2005.04916
ISBN (electronic)978-3-030-88853-4
Publication statusPublished - 2021

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer
Volume13038
ISSN (Print)0302-9743
ISSN (electronic)1611-3349

Abstract

In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.

Keywords

    cs.CC, F.1.1; F.1.3; F.4.1, Constant-depth circuit families, Computation over the reals, Descriptive complexity

ASJC Scopus subject areas

Cite this

A Logical Characterization of Constant-Depth Circuits over the Reals. / Barlag, Timon; Vollmer, Heribert.
Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. ed. / Alexandra Silva; Renata Wassermann; Ruy de Queiroz. Vol. abs/2005.04916 2021. p. 16-30 (Lecture Notes in Computer Science (LNCS); Vol. 13038).

Research output: Chapter in book/report/conference proceedingConference contributionResearchpeer review

Barlag, T & Vollmer, H 2021, A Logical Characterization of Constant-Depth Circuits over the Reals. in A Silva, R Wassermann & R de Queiroz (eds), Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. vol. abs/2005.04916, Lecture Notes in Computer Science (LNCS), vol. 13038, pp. 16-30. https://doi.org/10.1007/978-3-030-88853-4_2
Barlag, T., & Vollmer, H. (2021). A Logical Characterization of Constant-Depth Circuits over the Reals. In A. Silva, R. Wassermann, & R. de Queiroz (Eds.), Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings (Vol. abs/2005.04916, pp. 16-30). (Lecture Notes in Computer Science (LNCS); Vol. 13038). https://doi.org/10.1007/978-3-030-88853-4_2
Barlag T, Vollmer H. A Logical Characterization of Constant-Depth Circuits over the Reals. In Silva A, Wassermann R, de Queiroz R, editors, Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Vol. abs/2005.04916. 2021. p. 16-30. (Lecture Notes in Computer Science (LNCS)). Epub 2021 Oct 6. doi: 10.1007/978-3-030-88853-4_2
Barlag, Timon ; Vollmer, Heribert. / A Logical Characterization of Constant-Depth Circuits over the Reals. Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. editor / Alexandra Silva ; Renata Wassermann ; Ruy de Queiroz. Vol. abs/2005.04916 2021. pp. 16-30 (Lecture Notes in Computer Science (LNCS)).
Download
@inproceedings{9e0e118b14ff47f9ae3d2c9ba47ac0d0,
title = "A Logical Characterization of Constant-Depth Circuits over the Reals",
abstract = "In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions. ",
keywords = "cs.CC, F.1.1; F.1.3; F.4.1, Constant-depth circuit families, Computation over the reals, Descriptive complexity",
author = "Timon Barlag and Heribert Vollmer",
note = "Funding Information: Supported by DFG VO 630/8-1.",
year = "2021",
doi = "10.1007/978-3-030-88853-4_2",
language = "English",
isbn = "978-3-030-88852-7 ",
volume = "abs/2005.04916",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer",
pages = "16--30",
editor = "Alexandra Silva and Renata Wassermann and {de Queiroz}, Ruy",
booktitle = "Logic, Language, Information, and Computation",

}

Download

TY - GEN

T1 - A Logical Characterization of Constant-Depth Circuits over the Reals

AU - Barlag, Timon

AU - Vollmer, Heribert

N1 - Funding Information: Supported by DFG VO 630/8-1.

PY - 2021

Y1 - 2021

N2 - In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.

AB - In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.

KW - cs.CC

KW - F.1.1; F.1.3; F.4.1

KW - Constant-depth circuit families

KW - Computation over the reals

KW - Descriptive complexity

UR - http://www.scopus.com/inward/record.url?scp=85117486121&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-88853-4_2

DO - 10.1007/978-3-030-88853-4_2

M3 - Conference contribution

SN - 978-3-030-88852-7

VL - abs/2005.04916

T3 - Lecture Notes in Computer Science (LNCS)

SP - 16

EP - 30

BT - Logic, Language, Information, and Computation

A2 - Silva, Alexandra

A2 - Wassermann, Renata

A2 - de Queiroz, Ruy

ER -

By the same author(s)