×

Found 101 Documents (Results 1–100)

Functional lower bounds for restricted arithmetic circuits of depth four. (English) Zbl 07799592

Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 14, 15 p. (2021).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

BQP after 28 years (Invited Talk). (English) Zbl 07799579

Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 1, 1 p. (2021).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Quantum advantage with shallow circuits under arbitrary corruption. (English) Zbl 07788647

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 74, 16 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Cryptographic hardness under projections for time-bounded Kolmogorov complexity. (English) Zbl 07788627

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 54, 17 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Iterated lower bound formulas: a diagonalization-based approach to proof complexity. (English) Zbl 07765167

Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 234-247 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. (English) Zbl 07765166

Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 223-233 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Parallel algorithms for power circuits and the word problem of the Baumslag group. (English) Zbl 07724247

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 74, 24 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Black-box hypotheses and lower bounds. (English) Zbl 07724202

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Toward better depth lower bounds: the XOR-KRW conjecture. (English) Zbl 07711620

Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 38, 24 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Shadows of Newton polytopes. (English) Zbl 07711591

Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 9, 23 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

The (Generalized) orthogonality dimension of (Generalized) Kneser graphs: bounds and applications. (English) Zbl 07711590

Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 8, 15 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Hybrid quantum-classical circuit simplification with the ZX-calculus. (English) Zbl 1507.68114

Oh, Hakjoo (ed.), Programming languages and systems. 19th Asian symposium, APLAS 2021, Chicago, IL, USA, October 17–18, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13008, 121-139 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case. (English) Zbl 1498.68107

Wu, Weili (ed.) et al., Algorithmic aspects in information and management. 15th international conference, AAIM 2021, virtual event, December 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13153, 380-391 (2021).
MSC:  68Q06 68Q17 68Q27
PDFBibTeX XMLCite
Full Text: DOI

A logical characterization of constant-depth circuits over the reals. (English) Zbl 07547731

Silva, Alexandra (ed.) et al., Logic, language, information, and computation. 27th international workshop, WoLLIC 2021, virtual event, October 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13038, 16-30 (2021).
MSC:  03B70
PDFBibTeX XMLCite
Full Text: DOI arXiv

Verifying low-dimensional input neural networks via input quantization. (English) Zbl 1497.68310

Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 206-214 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exploiting verified neural networks via floating point numerical error. (English) Zbl 1497.68309

Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 191-205 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Static analysis of ReLU neural networks with tropical polyhedra. (English) Zbl 1497.68304

Drăgoi, Cezara (ed.) et al., Static analysis. 28th international symposium, SAS 2021, Chicago, IL, USA, October 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12913, 166-190 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Constructions for quantum indistinguishability obfuscation. (English) Zbl 1497.81039

Longa, Patrick (ed.) et al., Progress in cryptology – LATINCRYPT 2021. 7th international conference on cryptology and information security in Latin America, Bogotá, Colombia, October 6–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12912, 24-43 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Round efficient secure multiparty quantum computation with identifiable abort. (English) Zbl 1487.81034

Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12825, 436-466 (2021).
PDFBibTeX XMLCite
Full Text: DOI

On the impact of treewidth in the computational complexity of freezing dynamics. (English) Zbl 07495174

De Mol, Liesbeth (ed.) et al., Connecting with computability. 17th conference on computability in Europe, CiE 2021, virtual event, Ghent, Belgium, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12813, 260-272 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Timed Petri nets with reset for pipelined synchronous circuit design. (English) Zbl 1489.68166

Buchs, Didier (ed.) et al., Application and theory of Petri nets and concurrency. 42nd international conference, PETRI NETS 2021, virtual event, June 23–25, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12734, 55-75 (2021).
PDFBibTeX XMLCite
Full Text: DOI HAL

Genmul: generating architecturally complex multipliers to challenge formal verification tools. (English) Zbl 07410746

Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 177-191 (2021).
MSC:  68Q60 68Q06 94C11
PDFBibTeX XMLCite
Full Text: DOI

Hybrid control of Toffoli and Peres gates. (English) Zbl 07410745

Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 167-175 (2021).
MSC:  68Q06 94C11
PDFBibTeX XMLCite
Full Text: DOI

Translation techniques for reversible circuit synthesis with positive and negative controls. (English) Zbl 07410744

Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 143-165 (2021).
MSC:  68Q06 94C11
PDFBibTeX XMLCite
Full Text: DOI

Formal verification of integer multiplier circuits using algebraic reasoning: a survey. (English) Zbl 07410738

Drechsler, Rolf (ed.) et al., Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. Cham: Springer. 1-27 (2021).
MSC:  68V15 68Q06
PDFBibTeX XMLCite
Full Text: DOI

Formal semantics and verification of network-based biocomputation circuits. (English) Zbl 1472.68057

Henglein, Fritz (ed.) et al., Verification, model checking, and abstract interpretation. 22nd international conference, VMCAI 2021, Copenhagen, Denmark, January 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12597, 464-485 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Reservoir computing for forecasting large spatiotemporal dynamical systems. (English) Zbl 1482.68203

Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 117-138 (2021).
MSC:  68T05 37D45 68Q06
PDFBibTeX XMLCite
Full Text: DOI

On the characteristics and structures of dynamical systems suitable for reservoir computing. (English) Zbl 1482.68201

Nakajima, Kohei (ed.) et al., Reservoir computing. Theory, physical implementations, and applications. Singapore: Springer. Nat. Comput. Ser., 97-116 (2021).
MSC:  68T05 37N99 68Q06
PDFBibTeX XMLCite
Full Text: DOI

Recent findings in Boolean techniques. Selected papers from the 14th international workshop on Boolean problems, IWSBP, virtual, September 24–25, 2020. (English) Zbl 1470.94002

Cham: Springer (ISBN 978-3-030-68070-1/hbk; 978-3-030-68073-2/pbk; 978-3-030-68071-8/ebook). vii, 197 p. (2021).
PDFBibTeX XMLCite
Full Text: DOI

On the dependence of the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates on the number of additional inputs. (English. Russian original) Zbl 1499.68107

Discrete Math. Appl. 31, No. 1, 61-75 (2021); translation from Diskretn. Mat. 32, No. 1, 8-26 (2020).
MSC:  68Q06
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 3

Main Field

all top 3

Software