## Journal of the ACM

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

### Latest Issues

 69, No. 2 (2022) 69, No. 1 (2022) 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) ...and 49 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 8 Sudan, Madhu 7 Censor-Hillel, Keren 7 Ostrovsky, Rafail 7 Raz, Ran 7 Roughgarden, Tim 7 Vazirani, Vijay V. 6 Arora, Sanjeev 6 Aspnes, James 6 Elkin, Michael 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 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 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 Barenboim, Leonid 4 Bro Miltersen, Peter 4 Dwork, Cynthia 4 Goldwasser, Shafi 4 Gupta, Anupam 4 Guruswami, Venkatesan 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 Servedio, Rocco A. 4 Sharir, Micha 4 Shavit, Nir N. 4 Slivkins, Aleksandrs 4 Tardos, Gábor 4 Teng, Shang-Hua 4 Upfal, Eli 4 Woodruff, David P. 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 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 ...and 1,477 more Authors
all top 5

### Fields

 815 Computer science (68-XX) 140 Combinatorics (05-XX) 96 Operations research, mathematical programming (90-XX) 86 Mathematical logic and foundations (03-XX) 71 Information and communication theory, circuits (94-XX) 53 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 Statistics (62-XX) 20 Quantum theory (81-XX) 14 Linear and multilinear algebra; matrix theory (15-XX) 14 Biology and other natural sciences (92-XX) 11 Convex and discrete geometry (52-XX) 10 Number theory (11-XX) 6 Manifolds and cell complexes (57-XX) 5 General algebraic systems (08-XX) 4 General and overarching topics; collections (00-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 Algebraic geometry (14-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 Field theory and polynomials (12-XX) 2 Ordinary differential equations (34-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-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

793 Publications have been cited 17,286 times in 13,507 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
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
2009
Most tensor problems are NP-hard. Zbl 1281.68126
Hillar, Christopher J.; Lim, Lek-Heng
2013
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
Authoritative sources in a hyperlinked environment. Zbl 1065.68660
Kleinberg, Jon M.
1999
Branching time and abstraction in bisimulation semantics. Zbl 0882.68085
van Glabbeek, Rob J.; Weijland, W. Peter
1996
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
1998
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
2004
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
Closure properties of constraints. Zbl 0890.68064
Jeavons, Peter; Cohen, David; Gyssens, Marc
1997
Unconditional security in quantum cryptography. Zbl 1323.94128
Mayers, Dominic
2001
Indexing compressed text. Zbl 1323.68261
Ferragina, Paolo; Manzini, Giovanni
2005
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Zbl 1065.68666
Leighton, Tom; Rao, Satish
1999
An automata-theoretic approach to branching-time model checking. Zbl 1133.68376
Kupferman, Orna; Vardi, Moshe Y.; Wolper, Pierre
2000
The random oracle methodology, revisited. Zbl 1204.94063
Canetti, Ran; Goldreich, Oded; Halevi, Shai
2004
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
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
Quantum lower bounds by polynomials. Zbl 1127.68404
Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald
2001
Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
2009
The topological structure of asynchronous computability. Zbl 1161.68469
Herlihy, Maurice; Shavit, Nir
1999
A constructive proof of the general Lovász local lemma. Zbl 1300.60024
Moser, Robin A.; Tardos, Gábor
2010
Semiring-based constraint satisfaction and optimization. Zbl 0890.68032
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca
1997
Fast Monte-Carlo algorithms for finding low-rank approximations. Zbl 1125.65005
Frieze, Alan; Kannan, Ravi; Vempala, Santosh
2004
A dichotomy theorem for constraint satisfaction problems on a 3-element set. Zbl 1316.68057
Bulatov, Andrei A.
2006
Counterexample-guided abstraction refinement for symbolic model checking. Zbl 1325.68145
Clarke, Edmund; Grumberg, Orna; Jha, Somesh; Lu, Yuan; Veith, Helmut
2003
The benefits of relaxing punctuality. Zbl 0882.68021
Alur, Rajeev; Feder, Tomás; Henzinger, Thomas A.
1996
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Zbl 1064.92510
Hannenhalli, Sridhar; Pevzner, Pavel A.
1999
On the combinatorial and algebraic complexity of quantifier elimination. Zbl 0885.68070
Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise
1996
Speed is as powerful as clairvoyance. Zbl 1094.68529
Kalyanasundaram, Bala; Pruhs, Kirk
2000
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
1998
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 (im)possibility of obfuscating programs. Zbl 1281.68118
Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke
2012
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
Aggregating inconsistent information: ranking and clustering. Zbl 1325.68102
Ailon, Nir; Charikar, Moses; Newman, Alantha
2008
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
The complexity of homomorphism and constraint satisfaction problems seen from the other side. Zbl 1312.68101
Grohe, Martin
2007
On the online bin packing problem. Zbl 1326.68337
Seiden, Steven S.
2002
Adding nesting structure to words. Zbl 1325.68138
2009
Linear work suffix array construction. Zbl 1326.68111
Kärkkäinen, Juha; Sanders, Peter; Burkhardt, Stefan
2006
AdWords and generalized online matching. Zbl 1312.68239
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V.
2007
An analysis of the Burrows-Wheeler transform. Zbl 1323.68262
Manzini, Giovanni
2001
Software protection and simulation on oblivious RAMs. Zbl 0885.68041
Goldreich, Oded; Ostrovsky, Rafail
1996
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
Beyond the flow decomposition barrier. Zbl 1064.90567
Goldberg, Andrew V.; Rao, Satish
1998
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
On clusterings: good, bad and spectral. Zbl 1192.05160
Kannan, Ravi; Vempala, Santosh; Vetta, Adrian
2004
Polynomial-time data reduction for dominating set. Zbl 1192.68337
Alber, Jochen; Fellows, Michael R.; Niedermeier, Rolf
2004
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
1998
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
2013
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
1996
A simple min-cut algorithm. Zbl 0891.68071
Stoer, Mechthild; Wagner, Frank
1997
Scale-sensitive dimensions, uniform convergence, and learnability. Zbl 0891.68086
Alon, Noga; Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David
1997
The PCP theorem by gap amplification. Zbl 1292.68074
Dinur, Irit
2007
When are elections with few candidates hard to manipulate? Zbl 1292.91062
Conitzer, Vincent; Sandholm, Tuomas; Lang, Jérôme
2007
Expander flows, geometric embeddings and graph partitioning. Zbl 1325.68255
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh
2009
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
2004
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
2007
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
Efficient noise-tolerant learning from statistical queries. Zbl 1065.68605
Kearns, Michael
1998
A new approach to the minimum cut problem. Zbl 0882.68103
Karger, David R.; Stein, Clifford
1996
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Zbl 1327.68331
Avron, Haim; Toledo, Sivan
2011
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
Number-theoretic constructions of efficient pseudo-random functions. Zbl 1248.94086
Naor, Moni; Reingold, Omer
2004
Noise-tolerant learning, the parity problem, and the statistical query model. Zbl 1325.68114
Blum, Avrim; Kalai, Adam; Wasserman, Hal
2003
Separators for sphere-packings and nearest neighbor graphs. Zbl 0883.68100
Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A.
1997
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
2004
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Zbl 1321.68274
Dell, Holger; Van Melkebeek, Dieter
2014
Learning without concentration. Zbl 1333.68232
Mendelson, Shahar
2015
Constraint satisfaction problems solvable by local consistency methods. Zbl 1295.68126
Barto, Libor; Kozik, Marcin
2014
Approximating extent measures of points. Zbl 1204.68240
Agarwal, Pankaj K.; Har-Peled, Sariel; Varadarajan, Kasturi R.
2004
An improved exponential-time algorithm for $$k$$-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
2005
A modal analysis of staged computation. Zbl 1323.68107
Davies, Rowan; Pfenning, Frank
2001
On the impact of combinatorial structure on congestion games. Zbl 1325.91010
Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold
2008
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
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
2000
A theory of goal-oriented communication. Zbl 1281.94004
Goldreich, Oded; Juba, Brendan; Sudan, Madhu
2012
Efficient computation of representative families with applications in parameterized and exact algorithms. Zbl 1410.05212
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket
2016
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Zbl 1325.68169
Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil
2009
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1997
Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields. Zbl 1326.68336
Kleinberg, Jon; Tardos, Éva
2002
Exponential lower bounds for polytopes in combinatorial optimization. Zbl 1333.90107
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
2015
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
1999
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
Spatial isolation implies zero knowledge even in a quantum world. Zbl 07500721
Chiesa, Alessandro; Forbes, Michael A.; Gur, Tom; Spooner, Nicholas
2022
A framework for adversarially robust streaming algorithms. Zbl 07500723
Ben-Eliezer, Omri; Jayaram, Rajesh; Woodruff, David P.; Yogev, Eylon
2022
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 1491.68128
Zhuk, Dmitriy
2020
Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Zbl 1491.68067
Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola
2020
A simple and approximately optimal mechanism for an additive buyer. Zbl 07273095
Babaioff, Moshe; Immorlica, Nicole; Lucier, Brendan; Weinberg, S. Matthew
2020
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 1491.68092
Kratsch, Stefan; Wahlström, Magnus
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
2020
Differential equation invariance axiomatization. Zbl 07273077
Platzer, André; Tan, Yong Kiam
2020
Planar graph perfect matching is in NC. Zbl 1491.68131
Anari, Nima; Vazirani, Vijay V.
2020
Automating resolution is NP-hard. Zbl 1491.68078
Atserias, Albert; Müller, Moritz
2020
Detecting an odd hole. Zbl 1491.68141
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie
2020
Fully online matching. Zbl 1491.68271
Huang, Zhiyi; Kang, Ning; Tang, Zhihao Gavin; Wu, Xiaowei; Zhang, Yuhao; Zhu, Xue
2020
The log-approximate-rank conjecture is false. Zbl 1491.68073
2020
Forcing and calculi for hybrid logics. Zbl 07273096
Găină, Daniel
2020
Universally composable security. Zbl 1491.68036
Canetti, Ran
2020
Silence. Zbl 1491.68025
Goren, Guy; Moses, Yoram
2020
Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations. Zbl 1473.68121
Kowalski, Dariusz R.; Mosteiro, Miguel A.
2020
The power of shunning: efficient asynchronous Byzantine agreement revisited. Zbl 1491.68024
Bangalore, Laasya; Choudhury, Ashish; Patra, Arpita
2020
Distributed exact shortest paths in sublinear time. Zbl 1491.68266
Elkin, Michael
2020
Embeddability in $$R^3$$ is NP-hard. Zbl 1491.68079
de Mesmay, Arnaud; Rieck, Yo&rsquo;av; Sedgwick, Eric; Tancer, Martin
2020
Oracle-efficient online learning and auction design. Zbl 1491.68093
Dudík, Miroslav; Haghtalab, Nika; Luo, Haipeng; Schapire, Robert E.; Syrgkanis, Vasilis; Vaughan, Jennifer Wortman
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
Pseudorandomness from shrinkage. Zbl 1427.68096
Impagliazzo, Russell; Meka, Raghu; Zuckerman, David
2019
The salesman’s improved paths through forests. Zbl 1479.90180
Sebő, András; Zuylen, Anke Van
2019
Approaching 3/2 for the $$s$$-$$t$$-path TSP. Zbl 1427.90246
Traub, Vera; Vygen, Jens
2019
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
2019
Computing the homology of basic semialgebraic sets in weak exponential time. Zbl 1426.14016
Bürgisser, Peter; Cucker, Felipe; Lairez, Pierre
2019
The Weisfeiler-Leman dimension of planar graphs is at most 3. Zbl 1483.05048
Kiefer, Sandra; Ponomarenko, Ilia; Schweitzer, Pascal
2019
Tight bounds for undirected graph exploration with pebbles and multiple agents. Zbl 1473.68119
Disser, Yann; Hackfeld, Jan; Klimm, Max
2019
Hierarchical clustering. Objective functions and algorithms. Zbl 1473.62213
2019
Infinite-duration bidding games. Zbl 1448.91060
Avni, Guy; Henzinger, Thomas A.; Chonev, Ventsislav
2019
The Moser-Tardos framework with partial resampling. Zbl 1476.05197
Harris, David G.; Srinivasan, Aravind
2019
An unrestricted learning procedure. Zbl 1473.68156
Mendelson, Shahar
2019
Exact algorithms via monotone local search. Zbl 1427.68119
Fomin, Fedor V.; Gaspers, Serge; Lokshtanov, Daniel; Saurabh, Saket
2019
On the parameterized complexity of approximating dominating set. Zbl 1473.68099
Karthik, C. S.; Laekhanukit, Bundit; Manurangsi, Pasin
2019
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
2019
Shellability is NP-complete. Zbl 1473.68198
Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
2019
On the computability of conditional probability. Zbl 1477.03171
Ackerman, Nathanael L.; Freer, Cameron E.; Roy, Daniel M.
2019
White-box vs. black-box complexity of search problems: Ramsey and graph property testing. Zbl 1473.68096
Komargodski, Ilan; Naor, Moni; Yogev, Eylon
2019
Approximate counting, the Lovász local lemma, and inference in graphical models. Zbl 1427.68128
Moitra, Ankur
2019
Going higher in first-order quantifier alternation hierarchies on words. Zbl 1427.03050
Place, Thomas; Zeitoun, Marc
2019
Near-optimal linear decision trees for $$k$$-SUM and related problems. Zbl 1427.68060
Kane, Daniel M.; Lovett, Shachar; Moran, Shay
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
On the decidability of membership in matrix-exponential semigroups. Zbl 1481.20197
Ouaknine, Joël; Pouly, Amaury; Sousa-Pinto, João; Worrell, James
2019
From real-time logic to timed automata. Zbl 1473.68107
Ferrère, Thomas; Maler, Oded; Ničković, Dejan; Pnueli, Amir
2019
Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation. Zbl 1479.90162
Wirth, Fabian R.; Stüdli, Sonja; Yu, Jia Yuan; Corless, Martin; Shorten, Robert
2019
On the complexity of hazard-free circuits. Zbl 1473.94170
Ikenmeyer, Christian; Komarath, Balagopal; Lenzen, Christoph; Lysikov, Vladimir; Mokhov, Andrey; Sreenivasaiah, Karteek
2019
Bandits and experts in metric spaces. Zbl 1476.91073
Kleinberg, Robert; Slivkins, Aleksandrs; Upfal, Eli
2019
Online bipartite matching with amortized $$O(\log^2 n)$$ replacements. Zbl 1473.68217
Bernstein, Aaron; Holm, Jacob; Rotenberg, Eva
2019
An operational characterization of mutual information in algorithmic information theory. Zbl 1473.68100
Romashchenko, Andrei; Zimand, Marius
2019
Deciding context unification. Zbl 1473.68103
Jeż, Artur
2019
Computing the geometric intersection number of curves. Zbl 1473.68197
Despré, Vincent; Lazarus, Francis
2019
Capacity upper bounds for deletion-type channels. Zbl 1471.94018
Cheraghchi, Mahdi
2019
Bar induction is compatible with constructive type theory. Zbl 1427.03066
Rahli, Vincent; Bickford, Mark; Cohen, Liron; Constable, Robert L.
2019
Parallel Bayesian search with no coordination. Zbl 1427.68359
Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav
2019
Indistinguishability obfuscation from functional encryption. Zbl 1407.94087
Bitansky, Nir; Vaikuntanathan, Vinod
2018
Fair enough: guaranteeing approximate maximin shares. Zbl 1410.91314
Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
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
Full abstraction for probabilistic PCF. Zbl 1426.68035
Ehrhard, Thomas; Pagani, Michele; Tasson, Christine
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
Threesomes, degenerates, and love triangles. Zbl 1422.68112
Grønlund, Allan; Pettie, Seth
2018
Matroid secretary problems. Zbl 1425.68461
Babaioff, Moshe; Immorlica, Nicole; Kempe, David; Kleinberg, Robert
2018
The applied pi calculus, mobile values, new names, and secure communication. Zbl 1426.68037
Abadi, Martín; Blanchet, Bruno; Fournet, Cédric
2018
Spectral properties of hypergraph Laplacian and approximation algorithms. Zbl 1426.05163
Chan, T.-H. Hubert; Louis, Anand; Tang, Zhihao Gavin; Zhang, Chenzi
2018
Proving the incompatibility of efficiency and strategyproofness via SMT solving. Zbl 1425.68385
Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian
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
The parameterized complexity of the $$k$$-biclique problem. Zbl 1426.68131
Lin, Bingkai
2018
Solving optimization problems with diseconomies of scale via decoupling. Zbl 1426.90261
Makarychev, Konstantin; Sviridenko, Maxim
2018
Coin flipping of any constant bias implies one-way functions. Zbl 1426.94083
Berman, Itay; Haitner, Iftach; Tentes, Aris
2018
Worst-case optimal join algorithms. Zbl 1426.68081
Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri
2018
Optimal multi-way number partitioning. Zbl 1426.68313
Schreiber, Ethan L.; Korf, Richard E.; Moffitt, Michael D.
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
Reachability is in DynFO. Zbl 1426.68107
Datta, Samir; Kulkarni, Raghav; Mukherjee, Anish; Schwentick, Thomas; Zeume, Thomas
2018
Shuffles and circuits (on lower bounds for modern parallel computation). Zbl 1426.68105
Roughgarden, Tim; Vassilvitskii, Sergei; Wang, Joshua R.
2018
Excluded grid minors and efficient polynomial-time approximation schemes. Zbl 1426.68303
Fomin, Fedorr V.; Lokshtanov, Daniel; Saurabh, Saket
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
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
Discrete temporal constraint satisfaction problems. Zbl 1425.68135
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
2018
Analysing snapshot isolation. Zbl 1425.68094
Cerone, Andrea; Gotsman, Alexey
2018
Rumor spreading and conductance. Zbl 1426.68022
Chierichetti, Flavio; Giakkoupis, George; Lattanzi, Silvio; Panconesi, Alessandro
2018
The cost of unknown diameter in dynamic networks. Zbl 1426.68228
Yu, Haifeng; Zhao, Yuda; Jahja, Irvan
2018
Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system. Zbl 1426.68097
Grochow, Joshua A.; Pitassi, Toniann
2018
Unifying concurrent objects and distributed tasks. Interval-linearizability. Zbl 1426.68181
Castañeda, Armando; Rajsbaum, Sergio; Raynal, Michel
2018
Competitive algorithms from competitive equilibria, non-clairvoyant scheduling under polyhedral constraints. Zbl 1426.68309
Im, Sungjin; Kulkarni, Janardhan; Munagala, Kamesh
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
The freezing threshold for $$k$$-colourings of a random graph. Zbl 1426.05150
Molloy, Michael
2018
Minimization of tree patterns. Zbl 1426.68076
Czerwiński, Wojciech; Martens, Wim; Niewerth, Matthias; Parys, Paweł
2018
Settling the query complexity of non-adaptive junta testing. Zbl 1426.68295
Chen, Xi; Servedio, Rocco A.; Tan, Li-Yang; Waingarten, Erik; Xie, Jinyu
2018
Deciding first-order properties of nowhere dense graphs. Zbl 1426.68172
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian
2017
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
...and 693 more Documents
all top 5

### Cited by 16,560 Authors

 72 Xu, Dachuan 67 Saurabh, Saket 56 Fomin, Fedor V. 52 Epstein, Leah 50 Navarro, Gonzalo 44 Raynal, Michel 43 Goldreich, Oded 38 Lokshtanov, Daniel 37 Chatterjee, Krishnendu 35 Thilikos, Dimitrios M. 34 Rajsbaum, Sergio 33 Pilipczuk, Marcin L. 33 Pilipczuk, Michał 31 Du, Donglei 31 Kupferman, Orna 31 Paschos, Vangelis Th. 31 Wu, Chenchen 30 Niedermeier, Rolf 29 Živný, Stanislav 27 Jonsson, Peter A. 27 Levin, Asaf 27 Spirakis, Paul G. 26 Guerraoui, Rachid 26 Murano, Aniello 26 Rauch Henzinger, Monika 26 Rothe, Jörg-Matthias 26 Thankachan, Sharma V. 25 Fraigniaud, Pierre 25 Henzinger, Thomas A. 25 Servedio, Rocco A. 24 Chan, Timothy Moon-Yew 24 Guruswami, Venkatesan 24 Jansen, Bart M. P. 24 Panolan, Fahad 24 Ron, Dana 24 Zehavi, Meirav 23 Bodirsky, Manuel 23 Feige, Uriel 23 Gagie, Travis 23 Goldberg, Leslie Ann 23 Pelc, Andrzej 23 Roughgarden, Tim 23 Sau, Ignasi 23 Sharir, Micha 23 Vaikuntanathan, Vinod 23 Zhang, Dongmei 22 Fernau, Henning 22 Grohe, Martin 22 Guo, Jiong 22 Gupta, Anupam 22 Kowalski, Dariusz R. 22 Manthey, Bodo 22 Marx, Dániel 22 Neiman, Ofer 21 Cai, Jin-Yi 21 Caragiannis, Ioannis 21 Censor-Hillel, Keren 21 Cygan, Marek 21 Golovach, Petr A. 21 Hajiaghayi, Mohammad Taghi 21 Halldórsson, Magnús Mar 21 Ishai, Yuval 21 Kaplan, Haim 21 Mehlhorn, Kurt 21 Pass, Rafael 21 Pettie, Seth 20 Alon, Noga M. 20 Bergstra, Jan A. 20 Krokhin, Andrei A. 20 Martin, Barnaby D. 20 Raman, Venkatesh 20 Vempala, Santosh S. 20 Yoshida, Yuichi 19 Bulatov, Andrei A. 19 Chen, Hubie 19 Czumaj, Artur 19 Fox, Jacob 19 Gottlob, Georg 19 Libkin, Leonid O. 19 Lingas, Andrzej 19 Mendelson, Shahar 19 Nagarajan, Viswanath 19 Naor, Assaf 19 Pruhs, Kirk R. 19 Ravi, Ramamoorthi 19 Sahai, Amit 18 Albers, Susanne 18 Bansal, Nikhil 18 Bozzelli, Laura 18 Cooper, Martin C. 18 Eiter, Thomas 18 Kratsch, Stefan 18 Papadimitriou, Christos Harilaos 18 Peleg, David 18 Qiu, Daowen 18 Scarcello, Francesco 18 Sgall, Jiří 18 Shah, Rahul 18 Vardi, Moshe Ya’akov 18 Woodruff, David P. ...and 16,460 more Authors
all top 5

### Cited in 628 Journals

 1,228 Theoretical Computer Science 552 Algorithmica 404 Journal of Computer and System Sciences 347 SIAM Journal on Computing 329 Information and Computation 300 Information Processing Letters 298 Discrete Applied Mathematics 257 Theory of Computing Systems 244 Artificial Intelligence 203 Distributed Computing 180 Journal of Combinatorial Optimization 152 Mathematical Programming. Series A. Series B 132 SIAM Journal on Discrete Mathematics 115 European Journal of Operational Research 110 Computational Complexity 108 Journal of Cryptology 102 Journal of Discrete Algorithms 100 Operations Research Letters 95 Discrete & Computational Geometry 93 Computational Geometry 93 Logical Methods in Computer Science 89 Information Sciences 78 Annals of Mathematics and Artificial Intelligence 77 Mathematics of Operations Research 74 Journal of Automated Reasoning 73 Formal Methods in System Design 64 Acta Informatica 63 Journal of Symbolic Computation 63 Games and Economic Behavior 63 Theory and Practice of Logic Programming 61 Operations Research 61 Discrete Optimization 60 Quantum Information Processing 59 Discrete Mathematics 59 Machine Learning 59 International Journal of Foundations of Computer Science 57 Random Structures & Algorithms 57 Linear Algebra and its Applications 57 Journal of Machine Learning Research (JMLR) 55 Computers & Operations Research 54 The Annals of Statistics 51 Annals of Operations Research 50 International Journal of Approximate Reasoning 48 International Journal of Theoretical Physics 45 Journal of Scheduling 44 European Journal of Combinatorics 44 Journal of Logical and Algebraic Methods in Programming 43 SIAM Journal on Matrix Analysis and Applications 43 International Journal of Computational Geometry & Applications 43 Foundations of Computational Mathematics 40 Computer Science Review 39 MSCS. Mathematical Structures in Computer Science 39 Journal of Global Optimization 39 SIAM Journal on Scientific Computing 38 Journal of Complexity 38 Formal Aspects of Computing 38 Designs, Codes and Cryptography 38 The Electronic Journal of Combinatorics 38 Optimization Letters 35 Journal of the ACM 34 ACM Transactions on Computational Logic 33 Journal of Parallel and Distributed Computing 33 Combinatorics, Probability and Computing 31 Combinatorica 31 Computational Optimization and Applications 30 Journal of Combinatorial Theory. Series B 30 Neural Computation 29 Applied Mathematics and Computation 29 Constraints 28 Israel Journal of Mathematics 28 Journal of Computational and Applied Mathematics 27 Networks 27 Pattern Recognition 27 The Journal of Logic and Algebraic Programming 27 Algorithms 26 International Journal of Computer Vision 25 Automatica 25 SIAM Journal on Optimization 25 Data Mining and Knowledge Discovery 25 ACM Journal of Experimental Algorithmics 24 Physica A 24 Annals of Pure and Applied Logic 24 Applied and Computational Harmonic Analysis 24 Journal of Applied Logic 23 Journal of Mathematical Imaging and Vision 22 Journal of Functional Programming 22 INFORMS Journal on Computing 21 Journal of Computational Physics 21 The Journal of Artificial Intelligence Research (JAIR) 20 Fuzzy Sets and Systems 20 Journal of Scientific Computing 20 Electronic Journal of Statistics 19 Mathematics of Computation 19 Studia Logica 19 Real-Time Systems 19 The Annals of Applied Probability 18 Computing 18 Journal of Graph Algorithms and Applications 18 International Journal of Quantum Information 17 Communications in Mathematical Physics ...and 528 more Journals
all top 5

### Cited in 62 Fields

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