×

Found 5,248 Documents (Results 801–900)

Time-space hardness of learning sparse parities. (English) Zbl 1370.68132

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 1067-1080 (2017).
PDFBibTeX XMLCite
Full Text: DOI

An adaptive sublinear-time block sparse Fourier transform. (English) Zbl 1372.65360

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 702-715 (2017).
MSC:  65T50 65Y20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Local max-cut in smoothed polynomial time. (English) Zbl 1369.68226

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 429-437 (2017).
MSC:  68Q25 68T20 91A10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deciding parity games in quasipolynomial time. (English) Zbl 1369.68234

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 252-263 (2017).
MSC:  68Q25 91A43
PDFBibTeX XMLCite
Full Text: DOI

Homomorphisms are a good basis for counting small subgraphs. (English) Zbl 1369.05191

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 210-223 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Bounds for semi-disjoint bilinear forms in a unit-cost computational model. (English) Zbl 1460.68045

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 14th annual conference, TAMC 2017, Bern, Switzerland, April 20–22, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10185, 412-424 (2017).
PDFBibTeX XMLCite
Full Text: DOI

A fast deterministic detection of small pattern graphs in graphs without large cliques. (English) Zbl 1464.68290

Poon, Sheung-Hung (ed.) et al., WALCOM: algorithms and computation. 11th international conference and workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10167, 217-227 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Inferences in stochastic volatility models: a new simpler way. (English) Zbl 1407.62329

Sutradhar, Brajendra C. (ed.), Advances and challenges in parametric and semi-parametric analysis for correlated data. Proceedings of the 2015 international symposium in statistics, ISS 2015, St. John’s, Canada, July 6–8, 2015. Cham: Springer. Lect. Notes Stat. 218, 97-131 (2016).
MSC:  62M10 62P05 62E15
PDFBibTeX XMLCite
Full Text: DOI

Blocking optimal \(k\)-arborescences. (English) Zbl 1414.90302

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1682-1694 (2016).
MSC:  90C27 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Time vs. information tradeoffs for leader election in anonymous trees. (English) Zbl 1410.68058

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 600-609 (2016).
MSC:  68M14 68Q25 68W15
PDFBibTeX XMLCite
Full Text: DOI

General techniques for combinatorial approximation. (English) Zbl 1394.90496

Thulasiraman, Krishnaiyan (ed.) et al., Handbook of graph theory, combinatorial optimization, and algorithms. Boca Raton, FL: CRC Press (ISBN 978-1-58488-595-5/hbk; 978-1-4200-1107-4/ebook). Chapman & Hall/CRC Computer and Information Science Series, 1027-1034 (2016).
PDFBibTeX XMLCite

On the satisfiability of some simple probabilistic logics. (English) Zbl 1394.68169

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 56-65 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Stable matching games: manipulation via subgraph isomorphism. (English) Zbl 1391.68053

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 29, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Optimal composition ordering problems for piecewise linear functions. (English) Zbl 1388.68125

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 42, 13 p. (2016).
MSC:  68Q25 68R05 90B35
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computing the pattern waiting time: a revisit of the intuitive approach. (English) Zbl 1398.60063

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 39, 12 p. (2016).
MSC:  60G40 60J10 65Y20
PDFBibTeX XMLCite
Full Text: DOI

Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression. (English) Zbl 1398.68259

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 82, 16 p. (2016).
MSC:  68Q25 68Q17 94C10
PDFBibTeX XMLCite
Full Text: DOI

Circuit size lower bounds and #SAT upper bounds through a general framework. (English) Zbl 1398.68193

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 45, 16 p. (2016).
MSC:  68Q17 68Q25 94C10
PDFBibTeX XMLCite
Full Text: DOI

On existential MSO and its relation to ETH. (English) Zbl 1398.68179

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 42, 14 p. (2016).
MSC:  68Q15 03B15
PDFBibTeX XMLCite
Full Text: DOI

On the complexity landscape of connected \(f\)-factor problems. (English) Zbl 1398.68233

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 41, 14 p. (2016).
MSC:  68Q25 05C40 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Stable states of perturbed Markov chains. (English) Zbl 1398.68214

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 18, 14 p. (2016).
MSC:  68Q25 60J10 68Q87
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the fine-grained complexity of rainbow coloring. (English) Zbl 1397.68102

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 58, 16 p. (2016).
MSC:  68Q25 05C15 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exponential time paradigms through the polynomial time lens. (English) Zbl 1397.68097

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 36, 14 p. (2016).
MSC:  68Q25 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Mixed integer programming approach to multiprocessor job scheduling with setup times. (English) Zbl 1380.68074

Kochetov, Yury (ed.) et al., Discrete optimization and operations research. 9th international conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44913-5/pbk; 978-3-319-44914-2/ebook). Lecture Notes in Computer Science 9869, 298-308 (2016).
MSC:  68M20 90C10 90C60
PDFBibTeX XMLCite
Full Text: DOI

Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems. (English) Zbl 1387.68269

Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 52, 16 p. (2016).
MSC:  68U05 68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Efficient algorithms to decide tightness. (English) Zbl 1387.52008

Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 12, 15 p. (2016).
MSC:  52A30 55U10 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating dynamic time warping and edit distance for a pair of point sequences. (English) Zbl 1387.68226

Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 6, 16 p. (2016).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic complexity for the realization of an effective subshift by a sofic. (English) Zbl 1388.68134

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 110, 14 p. (2016).
MSC:  68Q25 05B45 37B10 37B50
PDFBibTeX XMLCite
Full Text: DOI

Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations. (English) Zbl 1388.68041

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 109, 15 p. (2016).
MSC:  68Q05 03D78 68Q15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic time-space trade-offs for \(k\)-SUM. (English) Zbl 1388.68127

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 58, 14 p. (2016).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parity separation: a scientifically proven method for permanent weight loss. (English) Zbl 1388.68221

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 47, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fractals for kernelization lower bounds, with an application to length-bounded cut problems. (English) Zbl 1388.68111

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 25, 14 p. (2016).
MSC:  68Q25 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI

Linear time algorithm for quantum 2SAT. (English) Zbl 1388.68064

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 15, 14 p. (2016).
MSC:  68Q12
PDFBibTeX XMLCite
Full Text: DOI arXiv

Subexponential time algorithms for embedding \(H\)-minor free graphs. (English) Zbl 1388.68103

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 9, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Tight tradeoffs for real-time approximation of longest palindromes in streams. (English) Zbl 1380.68475

Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 18, 13 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. (English) Zbl 1380.68234

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 2, 17 p. (2016).
MSC:  68Q25 03F20 68Q05 68Q10 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the uncontended complexity of anonymous consensus. (English) Zbl 1380.68040

Anceaume, Emmanuelle (ed.) et al., 19th international conference on principles of distributed systems, OPODIS 2015, Rennes, France, December 14–17, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-98-9). LIPIcs – Leibniz International Proceedings in Informatics 46, Article 12, 16 p. (2016).
MSC:  68M14 68Q25
PDFBibTeX XMLCite
Full Text: DOI

The coalescing-branching random walk on expanders and the dual epidemic process. (English) Zbl 1376.68105

Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 461-467 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Brief announcement: Space-time tradeoffs for distributed verification. (English) Zbl 1374.68270

Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 357-359 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exact algorithms via monotone local search. (English) Zbl 1375.68185

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 764-775 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating connectivity domination in weighted bounded-genus graphs. (English) Zbl 1376.68171

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 584-597 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Deterministic and probabilistic binary search in graphs. (English) Zbl 1376.68064

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 519-532 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Free-cut elimination in linear logic and an application to a feasible arithmetic. (English) Zbl 1370.03078

Regnier, Laurent (ed.) et al., 25th EACSL annual conference and 30th workshop on computer science logic, CSL’16, Marseille, France, August 29 – September 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-022-4). LIPIcs – Leibniz International Proceedings in Informatics 62, Article 40, 18 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Definability of Cai-Fürer-Immerman problems in choiceless polynomial time. (English) Zbl 1369.68222

Regnier, Laurent (ed.) et al., 25th EACSL annual conference and 30th workshop on computer science logic, CSL’16, Marseille, France, August 29 – September 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-022-4). LIPIcs – Leibniz International Proceedings in Informatics 62, Article 19, 17 p. (2016).
MSC:  68Q19 03C13 68Q15
PDFBibTeX XMLCite
Full Text: DOI

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

Biographic Reference

all top 3

Software