Page Content
There is no English translation for this web page.
Dr. Stefan Mengel
[1]- © Stefan Mengel
CRIL-CNRS/Université d'Artois
Faculté des Sciences Jean Perrin
rue Jean Souvraz, S.P. 18
F-62307 LENS Cedex
FRANCE Persönliche Homepage
www.cril.univ-artois.fr/~mengel/ [2]
Publikationen in der Arbeitsgruppe
| Citation key | M-Characterizing-Arithmetic-Circuit-Classes-By-Constraint-Satisfaction-Problems |
|---|---|
| Author | Stefan Mengel |
| Title of Book | In Proceedings of ICALP 2011 |
| Pages | 700-711 |
| Year | 2011 |
| Volume | 6755 |
| Publisher | Springer |
| Series | Lecture Notes in Computer Science |
| Abstract | We explore the expressivity of constraint satisfaction problems (CSPs) in the arithmetic circuit model. While CSPs are known to yield VNP-complete polynomials in the general case, we show that for different restrictions of the structure of the CSPs we get characterizations of different arithmetic circuit classes. In particular we give the first natural non-circuit characterization of VP, the class of polynomial families efficiently computable by arithmetic circuits. |
Back [5]
isser/persons/stefan_mengel.jpg
g/fachgebiet_algorithmische_algebra/v_menue/members/dr_
stefan_mengel/parameter/en/font3/minhilfe/?no_cache=1&a
mp;tx_sibibtex_pi1%5Bdownload_bibtex_uid%5D=1351078&
;tx_sibibtex_pi1%5Bcontentelement%5D=tt_content%3A72194
5
g/fachgebiet_algorithmische_algebra/v_menue/members/dr_
stefan_mengel/parameter/en/font3/minhilfe/
Zusatzinformationen / Extras
Quick Access:
Schnellnavigation zur Seite über Nummerneingabe
Auxiliary Functions
This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.
Copyright TU Berlin 2008