×

Found 140 Documents (Results 1–100)

Property B: two-coloring non-uniform hypergraphs. (English) Zbl 07799609

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 31, 8 p. (2021).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Improved explicit data structures in the bit-probe model using error-correcting codes. (English) Zbl 07559399

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 28, 12 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Minimizing branching vertices in distance-preserving subgraphs. (English) Zbl 07121062

van Bevern, René (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11532, 131-142 (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Distance-preserving subgraphs of interval graphs. (English) Zbl 1442.05140

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 39, 13 p. (2017).
MSC:  05C62 05C12 05C85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Set membership with non-adaptive bit probes. (English) Zbl 1402.68034

Vollmer, Heribert (ed.) et al., 34th symposium on theoretical aspects of computer science (STACS 2017), Hannover, Germany, March 8–11, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-028-6). LIPIcs – Leibniz International Proceedings in Informatics 66, Article 38, 13 p. (2017).
MSC:  68P05 68P20 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

The zero-error randomized query complexity of the pointer function. (English) Zbl 1393.68081

Lal, Akash (ed.) et al., 36th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2016), Chennai, India, December 13–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-027-9). LIPIcs – Leibniz International Proceedings in Informatics 65, Article 16, 13 p. (2016).
MSC:  68Q25 68P05 68Q05 68Q10 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Partition bound is quadratically tight for product distributions. (English) Zbl 1388.68119

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 135, 13 p. (2016).
MSC:  68Q25 68Q10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tight bounds for communication-assisted agreement distillation. (English) Zbl 1380.94067

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 6, 17 p. (2016).
MSC:  94A15 68Q10 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Coordination complexity: small information coordinating large populations. (English) Zbl 1334.68094

Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS’16, Cambridge, MA, USA, January 14–16, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4057-1). 281-290 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Set membership with a few bit probes. (English) Zbl 1372.68123

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 776-784 (2015).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

An entropy-based proof for the Moore bound for irregular graphs. (English) Zbl 1345.05048

Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 173-181 (2014).
MSC:  05C35 05C81
PDFBibTeX XMLCite
Full Text: DOI arXiv

More on a problem of Zarankiewicz. (English) Zbl 1260.05110

Chao, Kun-Mao (ed.) et al., Algorithms and computation. 23rd international symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-35260-7/pbk). Lecture Notes in Computer Science 7676, 257-266 (2012).
MSC:  05C69 05C35 68Q17
PDFBibTeX XMLCite
Full Text: DOI

IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2012). Selected papers based on the presentations at the 32nd conference, Hyderabad, India, December 15–17, 2012. (English) Zbl 1256.68007

LIPIcs – Leibniz International Proceedings in Informatics 18. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-47-7). xiv, 560 p., electronic. (2012).
MSC:  68-06 00B25
PDFBibTeX XMLCite
Full Text: Link Link

Streaming algorithms for 2-coloring uniform hypergraphs. (English) Zbl 1342.05186

Dehne, Frank (ed.) et al., Algorithms and data structures. 12th international symposium, WADS 2011, New York, NY, USA, August 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22299-3/pbk). Lecture Notes in Computer Science 6844, 667-678 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Online set packing and competitive scheduling of multi-part tasks. (English) Zbl 1315.68035

Proceedings of the 29th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC ’10, Zurich, Switzerland, July 25–28, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-888-9). 440-449 (2010).
PDFBibTeX XMLCite
Full Text: DOI

Data structures for storing small sets in the bitprobe model. (English) Zbl 1287.68031

de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-15780-6/pbk). Lecture Notes in Computer Science 6347, 159-170 (2010).
MSC:  68P05 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Finding duplicates in a data stream. (English) Zbl 1421.68191

Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 402-411 (2009).
MSC:  68W20 68W32 68W40
PDFBibTeX XMLCite
Full Text: Link

A tight lower bound for parity in noisy communication networks. (English) Zbl 1192.90034

Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 1056-1065 (2008).
MSC:  90B18
PDFBibTeX XMLCite

Minimizing average latency in oblivious routing. (English) Zbl 1192.90035

Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 200-207 (2008).
MSC:  90B18 68M20 90C35
PDFBibTeX XMLCite

Gap amplification in PCPs using lazy random walks. (English) Zbl 1223.68049

Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 96-107 (2006).
MSC:  68Q17 68Q87
PDFBibTeX XMLCite
Full Text: DOI

Zero error list-decoding capacity of the \(q/(q-1)\) channel. (English) Zbl 1177.94119

Arun-Kumar, S. (ed.) et al., FSTTCS 2006: Foundations of software technology and theoretical computer science. 26th international conference, Kolkata, India, December 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49994-7/pbk). Lecture Notes in Computer Science 4337, 129-138 (2006).
MSC:  94A24
PDFBibTeX XMLCite
Full Text: DOI

Tradeoffs in depth-two superconcentrators. (English) Zbl 1136.68458

Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 372-383 (2006).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI

Complete partitions of graphs. (English) Zbl 1297.05192

Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 860-869 (2005).
MSC:  05C70 68Q17 68W20
PDFBibTeX XMLCite

Bounds for error reduction with few quantum queries. (English) Zbl 1142.68334

Chekuri, Chandra (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 8th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2005, and 9th international workshop on randomization and computation, RANDOM 2005, Berkeley, CA, USA, August 22–24, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28239-4/pbk). Lecture Notes in Computer Science 3624, 245-256 (2005).
MSC:  68P15 68Q05 81P68
PDFBibTeX XMLCite
Full Text: DOI

On the power of random bases in Fourier sampling: Hidden subgroup problem in the Heisenberg group. (English) Zbl 1084.81022

Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 1399-1411 (2005).
MSC:  81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

On converting CNF to DNF. (English) Zbl 1124.06302

Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2003. 28th international symposium, MFCS 2003, Bratislava, Slovakia, August 25–29, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40671-9/pbk). Lect. Notes Comput. Sci. 2747, 612-621 (2003).
MSC:  06E30 94C10
PDFBibTeX XMLCite
Full Text: DOI

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. (English) Zbl 1092.68730

Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 717-724 (2003).
MSC:  68W15
PDFBibTeX XMLCite

A direct sum theorem in communication complexity via message compression. (English) Zbl 1039.68048

Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 300-315 (2003).
MSC:  68P30 68Q17 81P68
PDFBibTeX XMLCite
Full Text: Link

FST TCS 2003: Foundations of software technology and theoretical computer science. 23rd conference, Mumbai, India, December 15–17, 2003. Proceedings. (English) Zbl 1029.00064

Lecture Notes in Computer Science. 2914. Berlin: Springer. xiii, 446 p. (2003).
MSC:  00B25 68-06 68N30
PDFBibTeX XMLCite
Full Text: DOI Link

On the hardness of approximating minimum monopoly problems. (English) Zbl 1027.90100

Agrawal, Manindra (ed.) et al., FST TCS 2002: Foundations of software technology and theoretical computer science. 22nd conference, Kanpur, India, December 12-14, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2556, 277-288 (2002).
MSC:  90C35 68Q17 90C59
PDFBibTeX XMLCite
Full Text: Link

The quantum communication complexity of the pointer chasing problem: The bit version. (English) Zbl 1027.68065

Agrawal, Manindra (ed.) et al., FST TCS 2002: Foundations of software technology and theoretical computer science. 22nd conference, Kanpur, India, December 12-14, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2556, 218-229 (2002).
PDFBibTeX XMLCite
Full Text: Link

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