# zbMATH — the first resource for mathematics

## Journal of the ACM

 Short Title: J. ACM Publisher: Association for Computing Machinery (ACM), New York, NY ISSN: 0004-5411; 1557-735X/e Online: http://dl.acm.org/pub.cfm?id=J401 Predecessor: Journal of the Association for Computing Machinery Comments: Indexed cover-to-cover
 Documents Indexed: 853 Publications (since 1996) References Indexed: 65 Publications with 2,684 References.
all top 5

#### Latest Issues

 67, No. 5 (2020) 67, No. 4 (2020) 67, No. 3 (2020) 67, No. 2 (2020) 67, No. 1 (2020) 66, No. 6 (2019) 66, No. 5 (2019) 66, No. 4 (2019) 66, No. 3 (2019) 66, No. 2 (2019) 66, No. 1 (2019) 65, No. 6 (2018) 65, No. 5 (2018) 65, No. 4 (2018) 65, No. 3 (2018) 65, No. 2 (2018) 65, No. 1 (2018) 64, No. 6 (2017) 64, No. 5 (2017) 64, No. 4 (2017) 64, No. 3 (2017) 64, No. 2 (2017) 64, No. 1 (2017) 63, No. 6 (2017) 63, No. 5 (2016) 63, No. 4 (2016) 63, No. 3 (2016) 63, No. 2 (2016) 63, No. 1 (2016) 62, No. 6 (2015) 62, No. 5 (2015) 62, No. 4 (2015) 62, No. 3 (2015) 62, No. 2 (2015) 62, No. 1 (2015) 61, No. 6 (2014) 61, No. 5 (2014) 61, No. 4 (2014) 61, No. 3 (2014) 61, No. 2 (2014) 61, No. 1 (2014) 60, No. 6 (2013) 60, No. 5 (2013) 60, No. 4 (2013) 60, No. 3 (2013) 60, No. 2 (2013) 60, No. 1 (2013) 59, No. 6 (2012) 59, No. 5 (2012) 59, No. 4 (2012) 59, No. 3 (2012) 59, No. 2 (2012) 59, No. 1 (2012) 58, No. 6 (2011) 58, No. 5 (2011) 58, No. 4 (2011) 58, No. 3 (2011) 58, No. 2 (2011) 58, No. 1 (2010) 57, No. 6 (2010) 57, No. 5 (2010) 57, No. 4 (2010) 57, No. 3 (2010) 57, No. 2 (2010) 57, No. 1 (2009) 56, No. 6 (2009) 56, No. 5 (2009) 56, No. 4 (2009) 56, No. 3 (2009) 56, No. 2 (2009) 56, No. 1 (2009) 55, No. 6 (2008) 55, No. 5 (2008) 55, No. 4 (2008) 55, No. 3 (2008) 55, No. 2 (2008) 55, No. 1 (2008) 54, No. 6 (2007) 54, No. 5 (2007) 54, No. 4 (2007) 54, No. 3 (2007) 54, No. 2 (2007) 54, No. 1 (2007) 53, No. 6 (2006) 53, No. 5 (2006) 53, No. 4 (2006) 53, No. 3 (2006) 53, No. 2 (2006) 53, No. 1 (2006) 52, No. 6 (2005) 52, No. 5 (2005) 52, No. 4 (2005) 52, No. 3 (2005) 52, No. 2 (2005) 52, No. 1 (2005) 51, No. 6 (2004) 51, No. 5 (2004) 51, No. 4 (2004) 51, No. 3 (2004) 51, No. 2 (2004) ...and 47 more Volumes
all top 5

#### Authors

 12 Libkin, Leonid O. 11 Gottlob, Georg 10 Thorup, Mikkel 8 Attiya, Hagit 8 Goldreich, Oded 8 Kleinberg, Jon Michael 7 Ostrovsky, Rafail 7 Roughgarden, Tim 7 Sudan, Madhu 7 Vazirani, Vijay V. 6 Arora, Sanjeev 6 Aspnes, James 6 Censor-Hillel, Keren 6 Fomin, Fedor V. 6 Grohe, Martin 6 Kleinberg, Robert D. 6 Naor, Joseph Seffi 6 Naor, Moni 6 Papadimitriou, Christos Harilaos 6 Pettie, Seth 6 Raz, Ran 6 Schwentick, Thomas 6 Srinivasan, Aravind 6 Vempala, Santosh S. 5 Andrews, Matthew T. 5 Benedikt, Michael A. 5 Blum, Avrim L. 5 Chazelle, Bernard 5 Chen, Xi 5 Chuzhoy, Julia 5 Elkin, Michael 5 Fagin, Ronald 5 Ferragina, Paolo 5 Goldberg, Leslie Ann 5 Guerraoui, Rachid 5 Jerrum, Mark R. 5 Lenzen, Christoph 5 Segoufin, Luc 5 Suciu, Dan Mircea 5 Van den Bussche, Jan 5 Vazirani, Umesh V. 5 Vianu, Victor 5 Vitányi, Paul M. B. 5 Yannakakis, Mihalis 4 Abadi, Martín 4 Achlioptas, Dimitris 4 Agarwal, Pankaj Kumar 4 Alon, Noga M. 4 Alur, Rajeev 4 Ambainis, Andris 4 Awerbuch, Baruch 4 Babaioff, Moshe 4 Bro Miltersen, Peter 4 Dwork, Cynthia 4 Goldwasser, Shafi 4 Haeupler, Bernhard 4 Har-Peled, Sariel 4 Henzinger, Thomas A. 4 Italiano, Giuseppe Francesco 4 Kaplan, Haim 4 Kolaitis, Phokion G. 4 Kopparty, Swastik 4 Lokshtanov, Daniel 4 Manzini, Giovanni 4 Peleg, David 4 Rajsbaum, Sergio 4 Regev, Oded 4 Sahai, Amit 4 Saks, Michael E. 4 Saurabh, Saket 4 Schieber, Baruch 4 Schulman, Leonard J. 4 Sharir, Micha 4 Shavit, Nir N. 4 Slivkins, Aleksandrs 4 Tardos, Gábor 4 Teng, Shang-Hua 4 Upfal, Eli 4 Zhang, Lisa 4 Zwick, Uri 3 Arenas, Marcelo 3 Atserias, Albert 3 Balcan, Maria-Florina 3 Banerjee, Anindya 3 Bansal, Nikhil 3 Barak, Boaz 3 Barenboim, Leonid 3 Beame, Paul W. 3 Ben-Sasson, Eli 3 Bilardi, Gianfranco 3 Bodirsky, Manuel 3 Bshouty, Nader H. 3 Bulatov, Andrei A. 3 Cesa-Bianchi, Nicolò 3 Chan, T.-H. Hubert 3 Chan, Timothy Moon-Yew 3 Chandra, Tushar Deepak 3 Chatterjee, Krishnendu 3 Cygan, Marek 3 Deng, Xiao-Tie ...and 1,439 more Authors
all top 5

#### Fields

 801 Computer science (68-XX) 134 Combinatorics (05-XX) 94 Operations research, mathematical programming (90-XX) 82 Mathematical logic and foundations (03-XX) 68 Information and communication theory, circuits (94-XX) 50 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 29 Probability theory and stochastic processes (60-XX) 25 Numerical analysis (65-XX) 20 Quantum theory (81-XX) 18 Statistics (62-XX) 14 Biology and other natural sciences (92-XX) 13 Linear and multilinear algebra; matrix theory (15-XX) 11 Convex and discrete geometry (52-XX) 9 Number theory (11-XX) 4 General and overarching topics; collections (00-XX) 4 General algebraic systems (08-XX) 4 Algebraic geometry (14-XX) 4 Manifolds and cell complexes (57-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Associative rings and algebras (16-XX) 3 Group theory and generalizations (20-XX) 3 Functional analysis (46-XX) 3 General topology (54-XX) 3 Algebraic topology (55-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Field theory and polynomials (12-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Ordinary differential equations (34-XX) 1 Partial differential equations (35-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Fluid mechanics (76-XX) 1 Optics, electromagnetic theory (78-XX)

#### Citations contained in zbMATH Open

762 Publications have been cited 15,156 times in 11,946 Documents Cited by Year
A threshold of $$\ln n$$ for approximating set cover. Zbl 1065.68573
Feige, Uriel
1998
Approximation algorithms for metric facility location and $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417
Jain, Kamal; Vazirani, Vijay V.
2001
Robust principal component analysis? Zbl 1327.62369
Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John
2011
How bad is selfish routing? Zbl 1323.90011
Roughgarden, Tim; Tardos, Éva
2002
Alternating-time temporal logic. Zbl 1326.68181
Alur, Rajeev; Henzinger, Thomas A.; Kupferman, Orna
2002
Some optimal inapproximability results. Zbl 1127.68405
2001
Proof verification and the hardness of approximation problems. Zbl 1065.68570
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario
1998
Property testing and its connection to learning and approximation. Zbl 1065.68575
Goldreich, Oded; Goldwasser, Shafi; Ron, Dana
1998
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
2005
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Zbl 1064.90566
Arora, Sanjeev
1998
Most tensor problems are NP-hard. Zbl 1281.68126
Hillar, Christopher J.; Lim, Lek-Heng
2013
Branching time and abstraction in bisimulation semantics. Zbl 0882.68085
van Glabbeek, Rob J.; Weijland, W. Peter
1996
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
2009
Authoritative sources in a hyperlinked environment. Zbl 1065.68660
Kleinberg, Jon M.
1999
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
2004
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
1998
Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to $$\operatorname{DPLL}(T)$$. Zbl 1326.68164
Nieuwenhuis, Robert; Oliveras, Albert; Tinelli, Cesare
2006
Unreliable failure detectors for reliable distributed systems. Zbl 0885.68021
Chandra, Tushar Deepak; Toueg, Sam
1996
An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Zbl 1065.68650
Arya, Sunil; Mount, David M.; Netanyahu, Nathan S.; Silverman, Ruth; Wu, Angela Y.
1998
A combinatorial strongly polynomial algorithm for minimizing submodular functions. Zbl 1127.90402
Iwata, Satoru; Fleischer, Lisa; Fujishige, Satoru
2001
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Zbl 1192.90120
Spielman, Daniel A.; Teng, Shang-Hua
2004
Unconditional security in quantum cryptography. Zbl 1323.94128
Mayers, Dominic
2001
Closure properties of constraints. Zbl 0890.68064
Jeavons, Peter; Cohen, David; Gyssens, Marc
1997
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Zbl 1065.68666
Leighton, Tom; Rao, Satish
1999
Indexing compressed text. Zbl 1323.68261
Ferragina, Paolo; Manzini, Giovanni
2005
An automata-theoretic approach to branching-time model checking. Zbl 1133.68376
Kupferman, Orna; Vardi, Moshe Y.; Wolper, Pierre
2000
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060
Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V.
2003
Short proofs are narrow – resolution made simple. Zbl 1089.03507
Ben-Sasson, Eli; Wigderson, Avi
2001
Undirected connectivity in log-space. Zbl 1315.68156
Reingold, Omer
2008
Semiring-based constraint satisfaction and optimization. Zbl 0890.68032
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca
1997
The random oracle methodology, revisited. Zbl 1204.94063
Canetti, Ran; Goldreich, Oded; Halevi, Shai
2004
Fast Monte-Carlo algorithms for finding low-rank approximations. Zbl 1125.65005
Frieze, Alan; Kannan, Ravi; Vempala, Santosh
2004
The benefits of relaxing punctuality. Zbl 0882.68021
Alur, Rajeev; Feder, Tomás; Henzinger, Thomas A.
1996
The topological structure of asynchronous computability. Zbl 1161.68469
Herlihy, Maurice; Shavit, Nir
1999
Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
2009
A constructive proof of the general Lovász local lemma. Zbl 1300.60024
Moser, Robin A.; Tardos, Gábor
2010
Quantum lower bounds by polynomials. Zbl 1127.68404
Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald
2001
On the combinatorial and algebraic complexity of quantifier elimination. Zbl 0885.68070
Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise
1996
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Zbl 1064.92510
Hannenhalli, Sridhar; Pevzner, Pavel A.
1999
Counterexample-guided abstraction refinement for symbolic model checking. Zbl 1325.68145
Clarke, Edmund; Grumberg, Orna; Jha, Somesh; Lu, Yuan; Veith, Helmut
2003
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
1998
Speed is as powerful as clairvoyance. Zbl 1094.68529
Kalyanasundaram, Bala; Pruhs, Kirk
2000
A dichotomy theorem for constraint satisfaction problems on a 3-element set. Zbl 1316.68057
Bulatov, Andrei A.
2006
The weakest failure detector for solving Consensus. Zbl 0885.68022
Chandra, Tushar Deepak; Hadzilacos, Vassos; Toueg, Sam
1996
Simplify: a theorem prover for program checking. Zbl 1323.68462
Detlefs, David; Nelson, Greg; Saxe, James B.
2005
On-line routing of virtual circuits with applications to load balancing and machine scheduling. Zbl 0890.68014
Aspnes, James; Azar, Yossi; Fiat, Amos; Plotkin, Serge; Waarts, Orli
1997
Subexponential parameterized algorithms on bounded-genus graphs and $$H$$-minor-free graphs. Zbl 1326.05152
Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M.
2005
On the online bin packing problem. Zbl 1326.68337
Seiden, Steven S.
2002
An analysis of the Burrows-Wheeler transform. Zbl 1323.68262
Manzini, Giovanni
2001
Linear work suffix array construction. Zbl 1326.68111
Kärkkäinen, Juha; Sanders, Peter; Burkhardt, Stefan
2006
On the (im)possibility of obfuscating programs. Zbl 1281.68118
Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke
2012
Scale-sensitive dimensions, uniform convergence, and learnability. Zbl 0891.68086
Alon, Noga; Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David
1997
The complexity of homomorphism and constraint satisfaction problems seen from the other side. Zbl 1312.68101
Grohe, Martin
2007
On clusterings: good, bad and spectral. Zbl 1192.05160
Kannan, Ravi; Vempala, Santosh; Vetta, Adrian
2004
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
2009
Truth revelation in approximately efficient combinatorial auctions. Zbl 1326.91011
Lehmann, Daniel; O’Callaghan, Liadan Ita; Shoham, Yoav
2002
Beyond the flow decomposition barrier. Zbl 1064.90567
Goldberg, Andrew V.; Rao, Satish
1998
Polynomial-time data reduction for dominating set. Zbl 1192.68337
Alber, Jochen; Fellows, Michael R.; Niedermeier, Rolf
2004
AdWords and generalized online matching. Zbl 1312.68239
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V.
2007
Aggregating inconsistent information: ranking and clustering. Zbl 1325.68102
Ailon, Nir; Charikar, Moses; Newman, Alantha
2008
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
2004
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
1996
How to use expert advice. Zbl 0890.68066
Cesa-Bianchi, Nicolò; Freund, Yoav; Haussler, David; Helmbold, David P.; Schapire, Robert E.; Warmuth, Manfred K.
1997
Adding nesting structure to words. Zbl 1325.68138
2009
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
1998
When are elections with few candidates hard to manipulate? Zbl 1292.91062
Conitzer, Vincent; Sandholm, Tuomas; Lang, Jérôme
2007
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Zbl 1127.68408
Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
2001
A simple min-cut algorithm. Zbl 0891.68071
Stoer, Mechthild; Wagner, Frank
1997
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
2007
A unified approach to approximating resource allocation and scheduling. Zbl 1323.68564
Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch
2001
All pairs shortest paths using bridging sets and rectangular matrix multiplication. Zbl 1326.05157
Zwick, Uri
2002
The PCP theorem by gap amplification. Zbl 1292.68074
Dinur, Irit
2007
Expander flows, geometric embeddings and graph partitioning. Zbl 1325.68255
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh
2009
A new approach to the minimum cut problem. Zbl 0882.68103
Karger, David R.; Stein, Clifford
1996
Efficient noise-tolerant learning from statistical queries. Zbl 1065.68605
Kearns, Michael
1998
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
2013
Approximating extent measures of points. Zbl 1204.68240
Agarwal, Pankaj K.; Har-Peled, Sariel; Varadarajan, Kasturi R.
2004
Software protection and simulation on oblivious RAMs. Zbl 0885.68041
Goldreich, Oded; Ostrovsky, Rafail
1996
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Zbl 1327.68331
Avron, Haim; Toledo, Sivan
2011
A theory of goal-oriented communication. Zbl 1281.94004
Goldreich, Oded; Juba, Brendan; Sudan, Madhu
2012
Number-theoretic constructions of efficient pseudo-random functions. Zbl 1248.94086
Naor, Moni; Reingold, Omer
2004
A modal analysis of staged computation. Zbl 1323.68107
Davies, Rowan; Pfenning, Frank
2001
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
2004
Separators for sphere-packings and nearest neighbor graphs. Zbl 0883.68100
Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A.
1997
A differential approach to inference in Bayesian networks. Zbl 1325.68226
2003
The computational complexity of knot and link problems. Zbl 1065.68667
Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas
1999
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
1999
Noise-tolerant learning, the parity problem, and the statistical query model. Zbl 1325.68114
Blum, Avrim; Kalai, Adam; Wasserman, Hal
2003
Learning without concentration. Zbl 1333.68232
Mendelson, Shahar
2015
Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields. Zbl 1326.68336
Kleinberg, Jon; Tardos, Éva
2002
An improved exponential-time algorithm for $$k$$-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
2005
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Zbl 1321.68274
Dell, Holger; Van Melkebeek, Dieter
2014
On the impact of combinatorial structure on congestion games. Zbl 1325.91010
Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold
2008
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1997
Convex quadratic and semidefinite programming relaxations in scheduling. Zbl 1323.90024
Skutella, Martin
2001
A needed narrowing strategy. Zbl 1327.68141
Antoy, Sergio; Echahed, Rachid; Hanus, Michael
2000
Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Zbl 0904.68111
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
1997
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
2000
Deciding first-order properties of locally tree-decomposable structures. Zbl 1323.03014
Frick, Markus; Grohe, Martin
2001
Constraint satisfaction problems solvable by local consistency methods. Zbl 1295.68126
Barto, Libor; Kozik, Marcin
2014
Planar graphs have bounded queue-number. Zbl 1466.05047
Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R.
2020
A proof of the CSP dichotomy conjecture. Zbl 07273097
Zhuk, Dmitriy
2020
Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Zbl 07273073
Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola
2020
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 07273087
Kratsch, Stefan; Wahlström, Magnus
2020
A simple and approximately optimal mechanism for an additive buyer. Zbl 07273095
Babaioff, Moshe; Immorlica, Nicole; Lucier, Brendan; Weinberg, S. Matthew
2020
Detecting an odd hole. Zbl 07273076
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie
2020
Differential equation invariance axiomatization. Zbl 07273077
Platzer, André; Tan, Yong Kiam
2020
Planar graph perfect matching is in NC. Zbl 07273092
Anari, Nima; Vazirani, Vijay V.
2020
Forcing and calculi for hybrid logics. Zbl 07273096
Găină, Daniel
2020
Silence. Zbl 07273074
Goren, Guy; Moses, Yoram
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
2020
Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations. Zbl 07273082
Kowalski, Dariusz R.; Mosteiro, Miguel A.
2020
Distributed exact shortest paths in sublinear time. Zbl 07273086
Elkin, Michael
2020
Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Zbl 1427.91142
Devanur, Nikhil R.; Jain, Kamal; Sivan, Balasubramanian; Wilkens, Christopher A.
2019
The salesman’s improved paths through forests. Zbl 07165880
Sebő, András; Zuylen, Anke Van
2019
Pseudorandomness from shrinkage. Zbl 1427.68096
Impagliazzo, Russell; Meka, Raghu; Zuckerman, David
2019
Approaching 3/2 for the $$s$$-$$t$$-path TSP. Zbl 1427.90246
Traub, Vera; Vygen, Jens
2019
The Moser-Tardos framework with partial resampling. Zbl 07165888
Harris, David G.; Srinivasan, Aravind
2019
The Weisfeiler-Leman dimension of planar graphs is at most 3. Zbl 07165896
Kiefer, Sandra; Ponomarenko, Ilia; Schweitzer, Pascal
2019
Computing the homology of basic semialgebraic sets in weak exponential time. Zbl 1426.14016
Bürgisser, Peter; Cucker, Felipe; Lairez, Pierre
2019
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
2019
On the parameterized complexity of approximating dominating set. Zbl 07165885
Karthik, C. S.; Laekhanukit, Bundit; Manurangsi, Pasin
2019
Going higher in first-order quantifier alternation hierarchies on words. Zbl 1427.03050
Place, Thomas; Zeitoun, Marc
2019
Shellability is NP-complete. Zbl 07165873
Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
2019
On the computability of conditional probability. Zbl 07165875
Ackerman, Nathanael L.; Freer, Cameron E.; Roy, Daniel M.
2019
Infinite-duration bidding games. Zbl 1448.91060
Avni, Guy; Henzinger, Thomas A.; Chonev, Ventsislav
2019
Tight bounds for undirected graph exploration with pebbles and multiple agents. Zbl 07165892
Disser, Yann; Hackfeld, Jan; Klimm, Max
2019
An unrestricted learning procedure. Zbl 07165894
Mendelson, Shahar
2019
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
2019
Exact algorithms via monotone local search. Zbl 1427.68119
Fomin, Fedor V.; Gaspers, Serge; Lokshtanov, Daniel; Saurabh, Saket
2019
Approximate counting, the Lovász local lemma, and inference in graphical models. Zbl 1427.68128
Moitra, Ankur
2019
Parallel Bayesian search with no coordination. Zbl 1427.68359
Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav
2019
From real-time logic to timed automata. Zbl 07165871
Ferrère, Thomas; Maler, Oded; Ničković, Dejan; Pnueli, Amir
2019
Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation. Zbl 07165876
Wirth, Fabian R.; Stüdli, Sonja; Yu, Jia Yuan; Corless, Martin; Shorten, Robert
2019
On the complexity of hazard-free circuits. Zbl 07165877
Ikenmeyer, Christian; Komarath, Balagopal; Lenzen, Christoph; Lysikov, Vladimir; Mokhov, Andrey; Sreenivasaiah, Karteek
2019
Deciding context unification. Zbl 07165891
Jeż, Artur
2019
Fast learning requires good memory: a time-space lower bound for parity learning. Zbl 1426.68240
Raz, Ran
2019
Scaling exponential backoff: constant throughput, polylogarithmic channel-access attempts, and robustness. Zbl 1426.68021
Bender, Michael A.; Fineman, Jeremy T.; Gilbert, Seth; Young, Maxwell
2019
Fair enough: guaranteeing approximate maximin shares. Zbl 1410.91314
Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
2018
Indistinguishability obfuscation from functional encryption. Zbl 1407.94087
Bitansky, Nir; Vaikuntanathan, Vinod
2018
Non-malleable codes. Zbl 1409.94869
Dziembowski, Stefan; Pietrzak, Krzysztof; Wichs, Daniel
2018
Subcubic equivalences between path, matrix, and triangle problems. Zbl 1426.68133
Williams, Virginia Vassilevska; Williams, R. Ryan
2018
Bandits with knapsacks. Zbl 1425.68340
Badanidiyuru, Ashwinkumar; Kleinberg, Robert; Slivkins, Aleksandrs
2018
Spectral properties of hypergraph Laplacian and approximation algorithms. Zbl 1426.05163
Chan, T.-H. Hubert; Louis, Anand; Tang, Zhihao Gavin; Zhang, Chenzi
2018
Threesomes, degenerates, and love triangles. Zbl 1422.68112
Grønlund, Allan; Pettie, Seth
2018
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
2018
Path ORAM: an extremely simple oblivious RAM protocol. Zbl 1426.68008
Stefanov, Emil; Van Dijk, Marten; Shi, Elaine; Chan, T.-H. Hubert; Fletcher, Christopher; Ren, Ling; Yu, Xiangyao; Devadas, Srinivas
2018
The applied pi calculus, mobile values, new names, and secure communication. Zbl 1426.68037
Abadi, Martín; Blanchet, Bruno; Fournet, Cédric
2018
Full abstraction for probabilistic PCF. Zbl 1426.68035
Ehrhard, Thomas; Pagani, Michele; Tasson, Christine
2018
Matroid secretary problems. Zbl 1425.68461
Babaioff, Moshe; Immorlica, Nicole; Kempe, David; Kleinberg, Robert
2018
The parameterized complexity of the $$k$$-biclique problem. Zbl 1426.68131
Lin, Bingkai
2018
Coin flipping of any constant bias implies one-way functions. Zbl 1426.94083
Berman, Itay; Haitner, Iftach; Tentes, Aris
2018
Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity. Zbl 1426.68075
Bienvenu, Meghyn; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael
2018
Weakest precondition reasoning for expected runtimes of randomized algorithms. Zbl 1426.68298
Kaminski, Benjamin Lucien; Katoen, Joost-Pieter; Matheja, Christoph; Olmedo, Federico
2018
Decremental single-source shortest paths on undirected graphs in near-linear total update time. Zbl 1426.68215
Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon
2018
Proving the incompatibility of efficiency and strategyproofness via SMT solving. Zbl 1425.68385
Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian
2018
Analysing snapshot isolation. Zbl 1425.68094
Cerone, Andrea; Gotsman, Alexey
2018
Worst-case optimal join algorithms. Zbl 1426.68081
Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri
2018
Distributed $$(\Delta+1)$$-coloring in sublogarithmic rounds. Zbl 1426.68214
Harris, David G.; Schneider, Johannes; Su, Hsin-Hao
2018
Equivalence of deterministic top-down tree-to-string transducers is decidable. Zbl 1426.68154
Seidl, Helmut; Maneth, Sebastian; Kemper, Gregor
2018
Optimal multi-way number partitioning. Zbl 1426.68313
Schreiber, Ethan L.; Korf, Richard E.; Moffitt, Michael D.
2018
Reachability is in DynFO. Zbl 1426.68107
Datta, Samir; Kulkarni, Raghav; Mukherjee, Anish; Schwentick, Thomas; Zeume, Thomas
2018
Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system. Zbl 1426.68097
Grochow, Joshua A.; Pitassi, Toniann
2018
Shuffles and circuits (on lower bounds for modern parallel computation). Zbl 1426.68105
Roughgarden, Tim; Vassilvitskii, Sergei; Wang, Joshua R.
2018
Solving optimization problems with diseconomies of scale via decoupling. Zbl 1426.90261
Makarychev, Konstantin; Sviridenko, Maxim
2018
The freezing threshold for $$k$$-colourings of a random graph. Zbl 1426.05150
Molloy, Michael
2018
Discrete temporal constraint satisfaction problems. Zbl 1425.68135
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
2018
Excluded grid minors and efficient polynomial-time approximation schemes. Zbl 1426.68303
Fomin, Fedorr V.; Lokshtanov, Daniel; Saurabh, Saket
2018
Rumor spreading and conductance. Zbl 1426.68022
Chierichetti, Flavio; Giakkoupis, George; Lattanzi, Silvio; Panconesi, Alessandro
2018
Constant-rate coding for multiparty interactive communication is impossible. Zbl 1426.68016
Braverman, Mark; Efremenko, Klim; Gelles, Ran; Haeupler, Bernhard
2018
Embeddability in the 3-sphere is decidable. Zbl 1426.68276
Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
2018
Minimization of tree patterns. Zbl 1426.68076
Czerwiński, Wojciech; Martens, Wim; Niewerth, Matthias; Parys, Paweł
2018
The cost of unknown diameter in dynamic networks. Zbl 1426.68228
Yu, Haifeng; Zhao, Yuda; Jahja, Irvan
2018
On algebraic branching programs of small width. Zbl 1426.68089
Bringmann, Karl; Ikenmeyer, Christian; Zuiddam, Jeroen
2018
Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford. Zbl 1426.68211
Friedrichs, Stephan; Lenzen, Christoph
2018
A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Zbl 1426.68311
Safey El Din, Mohab; Schost, Éric
2017
The matching polytope has exponential extension complexity. Zbl 1426.90255
Rothvoss, Thomas
2017
Deciding first-order properties of nowhere dense graphs. Zbl 1426.68172
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian
2017
Faster polynomial multiplication over finite fields. Zbl 1426.68310
Harvey, David; Van Der Hoeven, Joris; Lecerf, Grégoire
2017
Low-rank approximation and regression in input sparsity time. Zbl 1426.65057
Clarkson, Kenneth L.; Woodruff, David P.
2017
The 4/3 additive spanner exponent is tight. Zbl 1410.68263
Abboud, Amir; Bodwin, Greg
2017
Near-optimal regret bounds for Thompson sampling. Zbl 1426.68293
Agrawal, Shipra; Goyal, Navin
2017
Communication steps for parallel query processing. Zbl 1426.68074
Beame, Paul; Koutris, Paraschos; Suciu, Dan
2017
On the switch Markov chain for perfect matchings. Zbl 1426.60097
Dyer, Martin; Jerrum, Mark; Müller, Haiko
2017
Complexity of counting CSP with complex weights. Zbl 1426.68114
Cai, Jin-Yi; Chen, Xi
2017
Qualitative determinacy and decidability of stochastic games with signals. Zbl 1427.91022
Bertrand, Nathalie; Genest, Blaise; Gimbert, Hugo
2017
Which is the fairest (rent division) of them all? Zbl 1427.91144
Gal, Ya&rsquo;akov (Kobi); Mash, Moshe; Procaccia, Ariel D.; Zick, Yair
2017
Optimal induced universal graphs and adjacency labeling for trees. Zbl 1426.68192
Alstrup, Stephen; Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs
2017
Separations in query complexity based on pointer functions. Zbl 1426.68109
Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris
2017
Homotopy-initial algebras in type theory. Zbl 1426.03016
Awodey, Steve; Gambino, Nicola; Sojakova, Kristina
2017
High-rate locally correctable and locally testable codes with sub-polynomial query complexity. Zbl 1426.94160
Kopparty, Swastik; Meir, Or; Ron-Zewi, Noga; Saraf, Shubhangi
2017
Plane formation by synchronous mobile robots in the three-dimensional Euclidean space. Zbl 1426.68278
Yamauchi, Yukiko; Uehara, Taichi; Kijima, Shuji; Yamashita, Masafumi
2017
Tight lower bounds on graph embedding problems. Zbl 1426.68099
Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz
2017
The complexity of non-monotone markets. Zbl 1427.91130
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
2017
An average-case depth hierarchy theorem for Boolean circuits. Zbl 1426.68098
Håstad, Johan; Rossman, Benjamin; Servedio, Rocco A.; Tan, Li-Yang
2017
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2017
Statistical algorithms and a lower bound for detecting planted cliques. Zbl 1397.68085
Feldman, Vitaly; Grigorescu, Elena; Reyzin, Lev; Vempala, Santosh S.; Xiao, Ying
2017
Veanes, Margus; Bjørner, Nikolaj; Nachmanson, Lev; Bereg, Sergey
2017
A distributed $$(2+\epsilon)$$-approximation for vertex cover in $$O(\frac{\log \Delta}{\epsilon\log\log\Delta})$$ rounds. Zbl 1426.68291
Bar-Yehuda, Reuven; Censor-Hillel, Keren; Schwartzman, Gregory
2017
Streaming tree transducers. Zbl 1426.68136
Alur, Rajeev; D&rsquo;Antoni, Loris
2017
...and 662 more Documents
all top 5

#### Cited by 14,945 Authors

 69 Xu, Dachuan 57 Saurabh, Saket 50 Epstein, Leah 50 Fomin, Fedor V. 46 Navarro, Gonzalo 40 Raynal, Michel 34 Chatterjee, Krishnendu 32 Goldreich, Oded 32 Lokshtanov, Daniel 31 Kupferman, Orna 31 Paschos, Vangelis Th. 30 Niedermeier, Rolf 30 Rajsbaum, Sergio 30 Thilikos, Dimitrios M. 29 Du, Donglei 29 Wu, Chenchen 28 Pilipczuk, Michał 27 Levin, Asaf 27 Pilipczuk, Marcin L. 26 Jonsson, Peter A. 26 Spirakis, Paul G. 25 Guerraoui, Rachid 24 Servedio, Rocco A. 23 Fraigniaud, Pierre 23 Pelc, Andrzej 23 Rauch Henzinger, Monika 23 Rothe, Jörg-Matthias 23 Roughgarden, Tim 23 Živný, Stanislav 22 Chan, Timothy Moon-Yew 22 Feige, Uriel 22 Fernau, Henning 22 Guo, Jiong 22 Henzinger, Thomas A. 22 Manthey, Bodo 22 Thankachan, Sharma V. 21 Grohe, Martin 21 Guruswami, Venkatesan 21 Jansen, Bart M. P. 21 Ron, Dana 21 Zhang, Dongmei 20 Bodirsky, Manuel 20 Caragiannis, Ioannis 20 Cygan, Marek 20 Gagie, Travis 20 Sau, Ignasi 20 Sharir, Micha 20 Vaikuntanathan, Vinod 19 Alon, Noga M. 19 Bergstra, Jan A. 19 Chen, Hubie 19 Czumaj, Artur 19 Hajiaghayi, Mohammad Taghi 19 Marx, Dániel 19 Murano, Aniello 19 Pettie, Seth 19 Raman, Venkatesh 19 Vempala, Santosh S. 18 Bansal, Nikhil 18 Bulatov, Andrei A. 18 Cai, Jin-Yi 18 Censor-Hillel, Keren 18 Eiter, Thomas 18 Fox, Jacob 18 Goldberg, Leslie Ann 18 Gottlob, Georg 18 Kaplan, Haim 18 Krokhin, Andrei A. 18 Libkin, Leonid O. 18 Lingas, Andrzej 18 Mehlhorn, Kurt 18 Mendelson, Shahar 18 Naor, Assaf 18 Neiman, Ofer 18 Panolan, Fahad 18 Scarcello, Francesco 18 Sgall, Jiří 18 Shah, Rahul 18 Vardi, Moshe Y. 18 Yoshida, Yuichi 18 Zehavi, Meirav 17 Cooper, Martin C. 17 Dósa, György 17 Golovach, Petr A. 17 Gupta, Anupam 17 Halldórsson, Magnús Mar 17 Khachay, Mikhail Yur’evich 17 Martin, Barnaby D. 17 Mossel, Elchanan 17 Pass, Rafael 17 Peleg, David 17 Qiu, Daowen 17 Segev, Danny 16 Albers, Susanne 16 Aspnes, James 16 Chekuri, Chandra S. 16 Demaine, Erik D. 16 Fellows, Michael Ralph 16 Jeavons, Peter G. 16 Korman, Amos ...and 14,845 more Authors
all top 5

#### Cited in 593 Journals

 1,174 Theoretical Computer Science 526 Algorithmica 393 Journal of Computer and System Sciences 308 Information and Computation 299 SIAM Journal on Computing 288 Discrete Applied Mathematics 287 Information Processing Letters 245 Theory of Computing Systems 234 Artificial Intelligence 194 Distributed Computing 169 Journal of Combinatorial Optimization 138 Mathematical Programming. Series A. Series B 115 SIAM Journal on Discrete Mathematics 108 Computational Complexity 107 European Journal of Operational Research 102 Journal of Discrete Algorithms 99 Journal of Cryptology 90 Discrete & Computational Geometry 90 Computational Geometry 88 Information Sciences 88 Operations Research Letters 77 Annals of Mathematics and Artificial Intelligence 70 Journal of Automated Reasoning 69 Logical Methods in Computer Science 66 Formal Methods in System Design 64 Mathematics of Operations Research 63 Theory and Practice of Logic Programming 61 Journal of Symbolic Computation 60 Quantum Information Processing 59 Acta Informatica 59 Discrete Mathematics 59 International Journal of Foundations of Computer Science 58 Machine Learning 57 Random Structures & Algorithms 57 Journal of Machine Learning Research (JMLR) 56 Games and Economic Behavior 56 Discrete Optimization 52 Computers & Operations Research 51 Linear Algebra and its Applications 46 International Journal of Theoretical Physics 46 International Journal of Approximate Reasoning 45 Operations Research 44 The Annals of Statistics 44 European Journal of Combinatorics 43 International Journal of Computational Geometry & Applications 42 Journal of Scheduling 42 Journal of Logical and Algebraic Methods in Programming 40 Annals of Operations Research 40 Foundations of Computational Mathematics 38 Journal of Complexity 38 SIAM Journal on Matrix Analysis and Applications 37 Formal Aspects of Computing 36 MSCS. Mathematical Structures in Computer Science 35 Journal of the ACM 34 Designs, Codes and Cryptography 34 ACM Transactions on Computational Logic 34 Computer Science Review 33 Journal of Parallel and Distributed Computing 33 Journal of Global Optimization 33 Combinatorics, Probability and Computing 32 SIAM Journal on Scientific Computing 32 The Electronic Journal of Combinatorics 31 Combinatorica 31 Optimization Letters 30 Neural Computation 30 Computational Optimization and Applications 29 Applied Mathematics and Computation 28 Constraints 27 Journal of Computational and Applied Mathematics 27 Networks 27 Pattern Recognition 27 The Journal of Logic and Algebraic Programming 27 Algorithms 26 Israel Journal of Mathematics 26 Journal of Combinatorial Theory. Series B 25 International Journal of Computer Vision 24 Automatica 24 Annals of Pure and Applied Logic 24 Applied and Computational Harmonic Analysis 24 Journal of Applied Logic 23 SIAM Journal on Optimization 22 Journal of Functional Programming 22 Data Mining and Knowledge Discovery 20 Fuzzy Sets and Systems 19 Journal of Computational Physics 19 Real-Time Systems 18 Mathematics of Computation 18 Studia Logica 18 The Annals of Applied Probability 18 Journal of Mathematical Imaging and Vision 18 International Journal of Quantum Information 18 Electronic Journal of Statistics 17 Computing 17 Journal of Applied Non-Classical Logics 17 Journal of Graph Algorithms and Applications 16 Communications in Mathematical Physics 16 Advances in Mathematics 16 International Journal of Computer Mathematics 16 INFORMS Journal on Computing 16 Mathematics in Computer Science ...and 493 more Journals
all top 5

#### Cited in 62 Fields

 8,037 Computer science (68-XX) 2,285 Operations research, mathematical programming (90-XX) 2,079 Combinatorics (05-XX) 1,056 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 992 Information and communication theory, circuits (94-XX) 917 Mathematical logic and foundations (03-XX) 631 Numerical analysis (65-XX) 524 Statistics (62-XX) 360 Probability theory and stochastic processes (60-XX) 360 Quantum theory (81-XX) 318 Linear and multilinear algebra; matrix theory (15-XX) 240 Biology and other natural sciences (92-XX) 185 Convex and discrete geometry (52-XX) 125 Number theory (11-XX) 97 Algebraic geometry (14-XX) 97 Systems theory; control (93-XX) 89 Order, lattices, ordered algebraic structures (06-XX) 77 Statistical mechanics, structure of matter (82-XX) 66 Group theory and generalizations (20-XX) 65 General algebraic systems (08-XX) 63 Functional analysis (46-XX) 60 Commutative algebra (13-XX) 60 Calculus of variations and optimal control; optimization (49-XX) 58 Manifolds and cell complexes (57-XX) 52 Partial differential equations (35-XX) 40 Geometry (51-XX) 39 Field theory and polynomials (12-XX) 39 Dynamical systems and ergodic theory (37-XX) 39 Algebraic topology (55-XX) 30 Approximations and expansions (41-XX) 30 Operator theory (47-XX) 28 Category theory; homological algebra (18-XX) 24 Differential geometry (53-XX) 22 History and biography (01-XX) 22 General topology (54-XX) 20 General and overarching topics; collections (00-XX) 18 Functions of a complex variable (30-XX) 18 Ordinary differential equations (34-XX) 18 Fluid mechanics (76-XX) 16 Associative rings and algebras (16-XX) 14 Real functions (26-XX) 14 Measure and integration (28-XX) 14 Mechanics of deformable solids (74-XX) 13 Global analysis, analysis on manifolds (58-XX) 13 Geophysics (86-XX) 11 Harmonic analysis on Euclidean spaces (42-XX) 6 Topological groups, Lie groups (22-XX) 6 Mechanics of particles and systems (70-XX) 6 Optics, electromagnetic theory (78-XX) 4 Several complex variables and analytic spaces (32-XX) 4 Difference and functional equations (39-XX) 3 Abstract harmonic analysis (43-XX) 3 Integral transforms, operational calculus (44-XX) 3 Relativity and gravitational theory (83-XX) 2 Nonassociative rings and algebras (17-XX) 2 Special functions (33-XX) 2 Astronomy and astrophysics (85-XX) 2 Mathematics education (97-XX) 1 Potential theory (31-XX) 1 Sequences, series, summability (40-XX) 1 Integral equations (45-XX) 1 Classical thermodynamics, heat transfer (80-XX)