×

Found 161 Documents (Results 1–100)

Robustly learning mixtures of \(k\) arbitrary Gaussians. (English) Zbl 07774413

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1234-1247 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Solving sparse linear systems faster than matrix multiplication. (English) Zbl 07788369

Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 504-521 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Reducing isotropy and volume to KLS: an \(O*(n^3\psi^2)\) volume algorithm. (English) Zbl 07765224

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

The communication complexity of optimization. (English) Zbl 07304129

Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1733-1752 (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Strong self-concordance and sampling. (English) Zbl 07298322

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1212-1222 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions. (English) Zbl 07650131

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 64, 12 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Random projection in the brain and computation with assemblies of neurons. (English) Zbl 07559100

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 57, 19 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Efficient convex optimization with oracles. (English) Zbl 1452.68272

Bárány, Imre (ed.) et al., Building bridges II. Mathematics of László Lovász. Conference in celebration of László Lovász’ 70th birthday, Budapest, Hungary, July 2–6, 2018. Berlin: Springer. Bolyai Soc. Math. Stud. 28, 317-335 (2019).
MSC:  68W20 68W40 90C25
PDFBibTeX XMLCite
Full Text: DOI

The Kannan-Lovász-Simonovits conjecture. (English) Zbl 1474.52005

Jerison, David (ed.) et al., Current developments in mathematics 2017. Papers based on selected lectures given at the current development mathematics conference, Harvard University, Cambridge, MA, USA, November 2017. Somerville, MA: International Press. 1-36 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Long term memory and the densest K-subgraph problem. (English) Zbl 1462.68041

Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 57, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. (English) Zbl 1429.65028

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1122-1129 (2018).
MSC:  65C40 60E15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. (English) Zbl 1429.65009

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1115-1121 (2018).
MSC:  65C05 65D18 65Y20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Adaptive matrix vector product. (English) Zbl 1410.68179

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). 2044-2060 (2017).
MSC:  68Q25 65F30 68W27
PDFBibTeX XMLCite
Full Text: DOI

Statistical query algorithms for mean vector estimation and stochastic convex optimization. (English) Zbl 1422.90031

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). 1265-1277 (2017).
MSC:  90C15 90C25 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Towards human computable passwords. (English) Zbl 1402.94073

Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 10, 47 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. (English) Zbl 1372.68012

LIPIcs – Leibniz International Proceedings in Informatics 81. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-044-6). xvi, 49 articles, not consecutively paged, electronic only, open access (2017).
PDFBibTeX XMLCite
Full Text: DOI Link

Geodesic walks in polytopes. (English) Zbl 1370.90146

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). 927-940 (2017).
MSC:  90C08 60G50
PDFBibTeX XMLCite
Full Text: DOI arXiv

Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm. (English) Zbl 1321.68434

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 539-548 (2015).
MSC:  68U05 68W20 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the complexity of random satisfiability problems with planted solutions (extended abstract). (English) Zbl 1321.68280

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 77-86 (2015).
MSC:  68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

A cubic algorithm for computing Gaussian volume. (English) Zbl 1421.68186

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1215-1228 (2014).
MSC:  68W20 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Integer feasibility of random polytopes: random integer programs. (English) Zbl 1364.90221

Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 449-458 (2014).
MSC:  90C10 52B12 90C15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fourier PCA and robust tensor decomposition. (English) Zbl 1315.68209

Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 584-593 (2014).
MSC:  68T05 15A69 65F30
PDFBibTeX XMLCite
Full Text: DOI arXiv

The approximate rank of a matrix and its algorithmic applications: approximate rank. (English) Zbl 1293.68136

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 675-684 (2013).
MSC:  68Q17 05C22 15A15 65F30 68U05 68W25 91A05
PDFBibTeX XMLCite
Full Text: DOI

Statistical algorithms and a lower bound for detecting planted cliques. (English) Zbl 1293.68142

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 655-664 (2013).
MSC:  68Q17 05C69
PDFBibTeX XMLCite
Full Text: DOI

Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. (English) Zbl 1421.68209

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1445-1456 (2012).
PDFBibTeX XMLCite
Full Text: arXiv Link

Randomly-oriented \(k\)-\(d\) trees adapt to intrinsic dimension. (English) Zbl 1354.68067

D’Souza, Deepak (ed.) et al., 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. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-47-7). LIPIcs – Leibniz International Proceedings in Informatics 18, 48-57 (2012).
MSC:  68P05
PDFBibTeX XMLCite
Full Text: DOI

Many sparse cuts via higher eigenvalues. (English) Zbl 1286.05095

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 1131-1140 (2012).
MSC:  05C50
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithms for implicit hitting set problems. (English) Zbl 1375.68214

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). 614-629 (2011).
PDFBibTeX XMLCite
Full Text: Link

An FPTAS for #knapsack and related counting problems. (English) Zbl 1292.68167

Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 817-826 (2011).
MSC:  68W25 68Q15 90C27
PDFBibTeX XMLCite
Full Text: DOI

Enumerative lattice algorithms in any norm via \(M\)-ellipsoid coverings. (English) Zbl 1292.68091

Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 580-589 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On noise-tolerant learning of sparse parities and related problems. (English) Zbl 1348.68194

Kivinen, Jyrki (ed.) et al., Algorithmic learning theory. 22nd international conference, ALT 2011, Espoo, Finland, October 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24411-7/pbk). Lecture Notes in Computer Science 6925. Lecture Notes in Artificial Intelligence, 413-424 (2011).
MSC:  68T05
PDFBibTeX XMLCite
Full Text: DOI

Semantic communication for simple goals is equivalent to on-line learning. (English) Zbl 1350.68220

Kivinen, Jyrki (ed.) et al., Algorithmic learning theory. 22nd international conference, ALT 2011, Espoo, Finland, October 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24411-7/pbk). Lecture Notes in Computer Science 6925. Lecture Notes in Artificial Intelligence, 277-291 (2011).
MSC:  68T05 68Q32 68W27
PDFBibTeX XMLCite
Full Text: DOI

Algorithmic extensions of Cheeger’s inequality to higher eigenvalues and partitions. (English) Zbl 1321.05152

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, 315-326 (2011).
MSC:  05C50 05C70 05C85
PDFBibTeX XMLCite
Full Text: DOI

Thin partitions, isoperimetric inequalities and a sampling algorithm for star shaped bodies. (English) Zbl 1288.90062

Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1630-1645 (2010).
MSC:  90C25 68W05 68Q17
PDFBibTeX XMLCite
Full Text: arXiv

Recent progress and open problems in algorithmic convex geometry. (English) Zbl 1245.52005

Lodaya, Kamal (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010), December 15–18, 2010, Chennai, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-23-1). LIPIcs – Leibniz International Proceedings in Informatics 8, 42-64, electronic only (2010).
PDFBibTeX XMLCite
Full Text: DOI Link

On Nash-equilibria of approximation-stable games. (English) Zbl 1310.91009

Kontogiannis, Spyros (ed.) et al., Algorithmic game theory. Third international symposium, SAGT 2010, Athens, Greece, October 18–20, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-16169-8/pbk). Lecture Notes in Computer Science 6386, 78-89 (2010).
MSC:  91A10 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Expanders via random spanning trees. (English) Zbl 1421.68100

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). 576-585 (2009).
MSC:  68R05 68R10 68W20
PDFBibTeX XMLCite
Full Text: Link

Sampling \(s\)-concave functions: the limit of convexity based isoperimetry. (English) Zbl 1255.90091

Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 420-433 (2009).
MSC:  90C25 26B25 60G50
PDFBibTeX XMLCite
Full Text: DOI

Random tensors and planted cliques. (English) Zbl 1254.05180

Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 406-419 (2009).
MSC:  05C80 05C05 05C69
PDFBibTeX XMLCite
Full Text: DOI arXiv

Isotropic PCA and affine-invariant clustering. (English) Zbl 1159.68542

Grötschel, Martin (ed.) et al., Building bridges. Between mathematics and computer science. Selected papers of the conferences held in Budapest, Hungary, August 5–9, 2008 and Keszthely, Hungary, August 11–15, 2008 and other research papers dedicated to László Lovász on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-540-85218-6/hbk). Bolyai Society Mathematical Studies 19, 241-281 (2008).
MSC:  68T10
PDFBibTeX XMLCite
Full Text: DOI Link

Logconcave random graphs. (English) Zbl 1231.68180

STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 779-788 (2008).
MSC:  68R10 05C80
PDFBibTeX XMLCite

A discriminative framework for clustering via similarity functions. (English) Zbl 1231.68192

STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 671-680 (2008).
MSC:  68T05 62H30
PDFBibTeX XMLCite

An efficient re-scaled perceptron algorithm for conic systems. (English) Zbl 1203.68137

Bshouty, Nader H. (ed.) et al., Learning theory. 20th annual conference on learning theory, COLT 2007, San Diego, CA, USA, June 13–15, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72925-9). Lecture Notes in Computer Science 4539. Lecture Notes in Artificial Intelligence, 393-408 (2007).
MSC:  68T05 90C05
PDFBibTeX XMLCite
Full Text: DOI Link

Local versus global properties of metric spaces (extended abstract). (English) Zbl 1192.90155

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 41-50 (2006).
MSC:  90C27 05C85
PDFBibTeX XMLCite
Full Text: DOI

Matrix approximation and projective clustering via volume sampling. (English) Zbl 1192.68889

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 1117-1126 (2006).
MSC:  68W25 15A03 62H30
PDFBibTeX XMLCite
Full Text: DOI

Adaptive sampling and fast low-rank matrix approximation. (English) Zbl 1155.68575

Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 292-303 (2006).
MSC:  68W25 68W20 15A03
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software