×

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

Publications by Year

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

Citations by Year