×

Found 414 Documents (Results 1–100)

The complexity of sharing a pizza. (English) Zbl 07788586

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 13, 15 p. (2021).
PDFBibTeX XMLCite
Full Text: DOI

Memory-sample lower bounds for learning parity with noise. (English) Zbl 07768405

Wootters, Mary (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 24th international conference, APPROX 2021, and 25th international conference, RANDOM 2021, University of Washington, Seattle, Washington, US (virtual conference), August 16–18, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 207, Article 60, 19 p. (2021).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

On two-pass streaming algorithms for maximum bipartite matching. (English) Zbl 07768364

Wootters, Mary (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 24th international conference, APPROX 2021, and 25th international conference, RANDOM 2021, University of Washington, Seattle, Washington, US (virtual conference), August 16–18, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 207, Article 19, 18 p. (2021).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX-hard. (English) Zbl 07741400

Lakin, Matthew R. (ed.) et al., 27th international conference on DNA computing and molecular programming. DNA 27, Oxford, UK (virtual conference), September 13–16, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 205, Article 9, 21 p. (2021).
MSC:  68Q07 68Q17 92D20
PDFBibTeX XMLCite
Full Text: DOI

Quantum sub-Gaussian mean estimator. (English) Zbl 07740905

Mutzel, Petra (ed.) et al., 29th annual European symposium on algorithms. ESA 2021, Lisbon, Portugal (virtual conference), September 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 204, Article 50, 17 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On prover-efficient public-coin emulation of interactive proofs. (English) Zbl 1517.94056

Tessaro, Stefano (ed.), 2nd conference on information-theoretic cryptography. ITC 2021, July 23–26, 2021, virtual conference. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 199, Article 3, 15 p. (2021).
MSC:  94A60 68Q17
PDFBibTeX XMLCite
Full Text: DOI

StoqMA meets distribution testing. (English) Zbl 07701524

Hsieh, Min-Hsiu (ed.), 16th conference on the theory of quantum computation, communication and cryptography, virtual conference, TQC 2021, July 5–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 197, Article 4, 22 p. (2021).
MSC:  81P68 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

New attacks on LowMC instances with a single plaintext/ciphertext pair. (English) Zbl 1514.94036

Tibouchi, Mehdi (ed.) et al., Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 13090, 303-331 (2021).
MSC:  94A60 68P25 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Respecting lower bounds in uniform lower and upper bounded facility location problem. (English) Zbl 07670485

Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 463-475 (2021).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI

Game of thieves and WERW-Kpath: two novel measures of node and edge centrality for mafia networks. (English) Zbl 1504.91213

Teixeira, Andreia Sofia (ed.) et al., Complex networks XII. Proceedings of the 12th conference on complex networks CompleNet 2021, May 24–26, 2021. Cham: Springer. Springer Proc. Complex., 12-23 (2021).
MSC:  91D30 68Q17
PDFBibTeX XMLCite
Full Text: DOI

The complexity of MinRank. (English) Zbl 1504.94111

Cojocaru, Alina Carmen (ed.) et al., Women in numbers Europe III. Research directions in number theory. Selected papers based on the presentations at the 3rd conference, WINE 3, La Hublais, Center in Cesson-Sévigné, Bretagne, France, August 26–30, 2019. Cham: Springer. Assoc. Women Math. Ser. 24, 163-169 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Extremal mild solutions of Hilfer fractional impulsive systems. (English) Zbl 1507.34067

Chadli, Ouayl (ed.) et al., Mathematical analysis and applications, MAA 2020. Selected papers based on the presentations at the conference, Jamshedpur, India, November 2–4, 2020. Singapore: Springer. Springer Proc. Math. Stat. 381, 67-80 (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

Maximizing energy efficiency for charger scheduling of WRSNs. (English) Zbl 1498.68039

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, 111-122 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Single machine scheduling with rejection to minimize the weighted makespan. (English) Zbl 1498.90092

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, 96-110 (2021).
PDFBibTeX XMLCite
Full Text: DOI

The complexity of finding a broadcast center. (English) Zbl 1498.68204

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, 57-70 (2021).
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of nucleolus computation for bipartite \(b\)-matching games. (English) Zbl 1492.91032

Caragiannis, Ioannis (ed.) et al., Algorithmic game theory. 14th international symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12885, 171-185 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Gerrymandering on graphs: computational complexity and parameterized algorithms. (English) Zbl 1491.91101

Caragiannis, Ioannis (ed.) et al., Algorithmic game theory. 14th international symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12885, 140-155 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computational hardness of optimal fair computation: beyond Minicrypt. (English) Zbl 1486.94128

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 II. Cham: Springer. Lect. Notes Comput. Sci. 12826, 33-63 (2021).
MSC:  94A60 68Q17 68P25
PDFBibTeX XMLCite
Full Text: DOI

Boolean ring cryptographic equation solving. (English) Zbl 1485.94110

Dunkelman, Orr (ed.) et al., Selected areas in cryptography. 27th international conference, Halifax, NS, Canada (virtual event), October 21–23, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12804, 252-272 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. (English) Zbl 1490.68151

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 608-622 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Sorting by multi-cut rearrangements. (English) Zbl 1490.68303

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 593-607 (2021).
PDFBibTeX XMLCite
Full Text: DOI HAL

The complexity of flow expansion and electrical flow expansion. (English) Zbl 1490.90084

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 431-441 (2021).
PDFBibTeX XMLCite
Full Text: DOI Link

Fair division is hard even for amicable agents. (English) Zbl 1492.91160

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 421-430 (2021).
MSC:  91B32 68Q17
PDFBibTeX XMLCite
Full Text: DOI

The multiple traveling salesman problem on spiders. (English) Zbl 1490.90253

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 337-348 (2021).
PDFBibTeX XMLCite
Full Text: DOI

On the terminal connection problem. (English) Zbl 1490.68150

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 278-292 (2021).
MSC:  68R10 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Complexity of limit-cycle problems in Boolean networks. (English) Zbl 1490.68117

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 135-146 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Balanced independent and dominating sets on colored interval graphs. (English) Zbl 1490.68147

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 89-103 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Tight bounds on subexponential time approximation of set cover and related problems. (English) Zbl 07495125

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 18th international workshop, WAOA 2020, virtual event, September 9–10, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12806, 159-173 (2021).
MSC:  68W25 68W27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Synthesis of Petri nets with restricted place-environments: classical and parameterized. (English) Zbl 1489.68169

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, 292-311 (2021).
MSC:  68Q85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable. (English) Zbl 1489.68168

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, 253-273 (2021).
MSC:  68Q85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Cryptanalysis of the binary permuted kernel problem. (English) Zbl 1497.94110

Sako, Kazue (ed.) et al., Applied cryptography and network security. 19th international conference, ACNS 2021, Kamakura, Japan, June 21–24, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12727, 396-423 (2021).
PDFBibTeX XMLCite
Full Text: DOI

The applications of object migration automaton (OMA)-memetic algorithm for solving NP-hard problems. (English) Zbl 1485.68221

Kordestani, Javidan Kazemi (ed.) et al., Advances in learning automata and intelligent optimization. Cham: Springer. Intell. Syst. Ref. Libr. 208, 195-252 (2021).
PDFBibTeX XMLCite
Full Text: DOI

A memetic model based on fixed structure learning automata for solving NP-hard problems. (English) Zbl 1485.68220

Kordestani, Javidan Kazemi (ed.) et al., Advances in learning automata and intelligent optimization. Cham: Springer. Intell. Syst. Ref. Libr. 208, 159-193 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 3

Main Field

all top 3

Software