×

Found 78 Documents (Results 1–78)

On the probabilistic degrees of symmetric Boolean functions. (English) Zbl 1527.68089

Chattopadhyay, Arkadev (ed.) et al., 39th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2019, Bombay, India, December 11–13, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 150, Article 28, 14 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Double threshold digraphs. (English) Zbl 1512.68227

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 69, 12 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Pseudorandom generators from polarizing random walks. (English) Zbl 1441.68149

Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 1, 21 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Recognizing read-once functions from depth-three formulas. (English) Zbl 1434.68200

Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 232-243 (2018).
MSC:  68Q25 06E30 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximately sampling elements with fixed rank in graded posets. (English) Zbl 1410.68395

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1828-1838 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Polynomials, quantum query complexity, and Grothendieck’s inequality. (English) Zbl 1380.68184

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 25, 19 p. (2016).
MSC:  68Q12 06E30 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

The next whisky bar. (English) Zbl 1475.68136

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 11th international computer science symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9–13, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9691, 41-56 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Topological aspects of matrix abduction. II. (English) Zbl 1376.06003

Koslow, Arnold (ed.) et al., The road to universal logic. Festschrift for the 50th birthday of Jean-Yves Béziau. Volume II. New York, NY: Birkhäuser/Springer (ISBN 978-3-319-15367-4/pbk; 978-3-319-15368-1/ebook). Studies in Universal Logic, 357-385 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Covering partial cubes with zones. (English) Zbl 1343.05119

Akiyama, Jin (ed.) et al., Discrete and computational geometry and graphs. 16th Japanese conference, JCDCGG 2013, Tokyo, Japan, September 17–19, 2013. Revised selected papers. Cham: Springer (ISBN 978-3-319-13286-0/pbk; 978-3-319-13287-7/ebook). Lecture Notes in Computer Science 8845, 1-13 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On maximum rank aggregation problems. (English) Zbl 1407.68201

Lecroq, Thierry (ed.) et al., Combinatorial algorithms. 24th international workshop, IWOCA 2013, Rouen, France, July 10–12, 2013. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8288, 14-27 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Tight lower bounds for testing linear isomorphism. (English) Zbl 1405.68128

Raghavendra, Prasad (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 16th international workshop, APPROX 2013, and 17th international workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40327-9/pbk). Lecture Notes in Computer Science 8096, 559-574 (2013).
PDFBibTeX XMLCite
Full Text: DOI

On the isomorphism problem for decision trees and decision lists. (English) Zbl 1368.68218

Gąsieniec, Leszek (ed.) et al., Fundamentals of computation theory. 19th international symposium, FCT 2013, Liverpool, UK, August 19–21, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40163-3/pbk). Lecture Notes in Computer Science 8070, 16-27 (2013).
PDFBibTeX XMLCite
Full Text: DOI

A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry. (English) Zbl 1336.68261

Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-39205-4/pbk). Lecture Notes in Computer Science 7965, 376-387 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Bounding the randomized decision tree complexity of read-once Boolean functions. (English) Zbl 1376.68057

Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1729-1744 (2011).
PDFBibTeX XMLCite
Full Text: Link

Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity. (English) Zbl 1343.68305

Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 664-675 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Lattices and maximum flow algorithms in planar graphs. (English) Zbl 1310.05201

Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 324-335 (2010).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Testing Boolean function isomorphism. (English) Zbl 1305.68327

Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 394-405 (2010).
MSC:  68W20 06E30 68Q17 94C10
PDFBibTeX XMLCite
Full Text: DOI

Finding a level ideal of a poset. (English) Zbl 1248.68220

Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 317-327 (2009).
PDFBibTeX XMLCite
Full Text: DOI

Variable influences in conjunctive normal forms. (English) Zbl 1247.94075

Kullmann, Oliver (ed.), Theory and applications of satisfiability testing – SAT 2009. 12th international conference, SAT 2009, Swansea, UK, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02776-5/pbk). Lecture Notes in Computer Science 5584, 101-113 (2009).
MSC:  94C10 06E30 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

On-line chain partitioning as a model for real-time scheduling. (English) Zbl 1272.06005

Lescanne, Pierre (ed.) et al., Proceedings of the 2nd workshop on computational logic and applications (CLA 2004), Lyon, France, June 17–18, 2004. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 140, 15-29 (2005).
PDFBibTeX XMLCite
Full Text: Link

Monotonicity testing over general poset domains. (English) Zbl 1192.68359

Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 474-483, electronic only (2002).
PDFBibTeX XMLCite
Full Text: DOI

Complexity estimations of satisfiability of systems of Boolean equations of special classes. (English) Zbl 1029.06009

Algebra, geometry and their applications. Seminar proceedings, Yerevan State University, Yerevan, Armenia. Vol. 2, 2002. Yerevan: Yerevan State University Press. 19-25 (2002).
MSC:  06E30 68Q17 68Q25
PDFBibTeX XMLCite

Filter Results by …

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software