×

Found 19,077 Documents (Results 801–900)

Component stability in low-space massively parallel computation. (English) Zbl 07824226

Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 481-491 (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Brief announcement. A randomness-efficient massively parallel algorithm for connectivity. (English) Zbl 07824221

Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 431-433 (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI

Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. (English) Zbl 07824207

Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 283-293 (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Classification of OBDD size for monotone 2-CNFs. (English) Zbl 07803603

Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 25, 15 p. (2021).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Long paths make pattern-counting hard, and deep trees make it Harder. (English) Zbl 07803600

Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 22, 17 p. (2021).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Twin-width and polynomial kernels. (English) Zbl 07803588

Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 10, 16 p. (2021).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

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

Lower bounds for induced cycle detection in distributed computing. (English) Zbl 07788631

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 58, 19 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Identity testing under label mismatch. (English) Zbl 07788628

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 55, 17 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Streaming algorithms for graph \(k\)-matching with optimal or near-optimal update time. (English) Zbl 07788621

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 48, 17 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Brief announcement: probabilistic indistinguishability and the quality of validity in Byzantine agreement. (English) Zbl 07774308

Gilbert, Seth (ed.), 35th international symposium on distributed computing, DISC 2021, Freiburg, Germany (virtual conference) October 4–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 209, Article 57, 4 p. (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Extension-based proofs for synchronous message passing. (English) Zbl 07774287

Gilbert, Seth (ed.), 35th international symposium on distributed computing, DISC 2021, Freiburg, Germany (virtual conference) October 4–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 209, Article 36, 17 p. (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI

Ruling sets in random order and adversarial streams. (English) Zbl 07774257

Gilbert, Seth (ed.), 35th international symposium on distributed computing, DISC 2021, Freiburg, Germany (virtual conference) October 4–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 209, Article 6, 18 p. (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds for shared-memory leader election under bounded write contention. (English) Zbl 07774255

Gilbert, Seth (ed.), 35th international symposium on distributed computing, DISC 2021, Freiburg, Germany (virtual conference) October 4–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 209, Article 4, 17 p. (2021).
MSC:  68M14 68W15
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

The complexity of constrained min-max optimization. (English) Zbl 07765262

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). 1466-1478 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Universally-optimal distributed algorithms for known topologies. (English) Zbl 07765240

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). 1166-1179 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

The limits of pan privacy and shuffle privacy for learning and estimation. (English) Zbl 07765233

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). 1081-1094 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lower bounds for monotone arithmetic circuits via communication complexity. (English) Zbl 07765210

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). 786-799 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Almost optimal super-constant-pass streaming lower bounds for reachability. (English) Zbl 07765194

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). 570-583 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. (English) Zbl 07765171

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). 283-291 (2021).
MSC:  68Qxx
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

Automating algebraic proof systems is NP-hard. (English) Zbl 07765165

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). 209-222 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Data structures lower bounds and popular conjectures. (English) Zbl 07740894

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 39, 15 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Minimum common string partition: exact algorithms. (English) Zbl 07740890

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 35, 16 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Matching patterns with variables under Hamming distance. (English) Zbl 07724221

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 48, 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

A stress-free sum-of-squares lower bound for coloring. (English) Zbl 07711605

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 23, 21 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Branching programs with bounded repetitions and flow formulas. (English) Zbl 07711599

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 17, 25 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

A lower bound on determinantal complexity. (English) Zbl 07711586

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 4, 12 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

On the security of proofs of sequential work in a post-quantum world. (English) Zbl 1527.81039

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 22, 27 p. (2021).
MSC:  81P94 94A60 81Q93
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

More communication lower bounds for information-theoretic MPC. (English) Zbl 1517.94088

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 2, 18 p. (2021).
MSC:  94A60 68P25 68M14
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

Near-optimal decentralized algorithms for saddle point problems over time-varying networks. (English) Zbl 1527.90252

Olenev, Nicholas N. (ed.) et al., Optimization and applications. 12th international conference, OPTIMA 2021, Petrovac, Montenegro, September 27 – October 1, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13078, 246-257 (2021).
MSC:  90C47 90B10 90C25
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

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

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software