×

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: 64 Publications with 2,666 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

750 Publications have been cited 14,657 times in 11,557 Documents Cited by Year
A threshold of \(\ln n\) for approximating set cover. Zbl 1065.68573
Feige, Uriel
395
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.
313
2001
Robust principal component analysis? Zbl 1327.62369
Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John
274
2011
How bad is selfish routing? Zbl 1323.90011
Roughgarden, Tim; Tardos, Éva
240
2002
Some optimal inapproximability results. Zbl 1127.68405
Håstad, Johan
221
2001
Alternating-time temporal logic. Zbl 1326.68181
Alur, Rajeev; Henzinger, Thomas A.; Kupferman, Orna
218
2002
Proof verification and the hardness of approximation problems. Zbl 1065.68570
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario
203
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
175
2005
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Zbl 1064.90566
Arora, Sanjeev
157
1998
Most tensor problems are NP-hard. Zbl 1281.68126
Hillar, Christopher J.; Lim, Lek-Heng
151
2013
Branching time and abstraction in bisimulation semantics. Zbl 0882.68085
van Glabbeek, Rob J.; Weijland, W. Peter
140
1996
Authoritative sources in a hyperlinked environment. Zbl 1065.68660
Kleinberg, Jon M.
136
1999
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
133
2009
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
128
1998
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
126
2004
Unreliable failure detectors for reliable distributed systems. Zbl 0885.68021
Chandra, Tushar Deepak; Toueg, Sam
119
1996
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
119
2006
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.
117
1998
A combinatorial strongly polynomial algorithm for minimizing submodular functions. Zbl 1127.90402
Iwata, Satoru; Fleischer, Lisa; Fujishige, Satoru
115
2001
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Zbl 1192.90120
Spielman, Daniel A.; Teng, Shang-Hua
111
2004
Unconditional security in quantum cryptography. Zbl 1323.94128
Mayers, Dominic
106
2001
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Zbl 1065.68666
Leighton, Tom; Rao, Satish
103
1999
Closure properties of constraints. Zbl 0890.68064
Jeavons, Peter; Cohen, David; Gyssens, Marc
102
1997
Indexing compressed text. Zbl 1323.68261
Ferragina, Paolo; Manzini, Giovanni
96
2005
An automata-theoretic approach to branching-time model checking. Zbl 1133.68376
Kupferman, Orna; Vardi, Moshe Y.; Wolper, Pierre
95
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.
89
2003
Short proofs are narrow – resolution made simple. Zbl 1089.03507
Ben-Sasson, Eli; Wigderson, Avi
88
2001
Semiring-based constraint satisfaction and optimization. Zbl 0890.68032
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca
87
1997
Undirected connectivity in log-space. Zbl 1315.68156
Reingold, Omer
85
2008
Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
83
2009
The topological structure of asynchronous computability. Zbl 1161.68469
Herlihy, Maurice; Shavit, Nir
82
1999
Fast Monte-Carlo algorithms for finding low-rank approximations. Zbl 1125.65005
Frieze, Alan; Kannan, Ravi; Vempala, Santosh
82
2004
On the combinatorial and algebraic complexity of quantifier elimination. Zbl 0885.68070
Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise
81
1996
Quantum lower bounds by polynomials. Zbl 1127.68404
Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald
81
2001
The random oracle methodology, revisited. Zbl 1204.94063
Canetti, Ran; Goldreich, Oded; Halevi, Shai
80
2004
The benefits of relaxing punctuality. Zbl 0882.68021
Alur, Rajeev; Feder, Tomás; Henzinger, Thomas A.
80
1996
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Zbl 1064.92510
Hannenhalli, Sridhar; Pevzner, Pavel A.
79
1999
A constructive proof of the general Lovász local lemma. Zbl 1300.60024
Moser, Robin A.; Tardos, Gábor
79
2010
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
77
1998
Speed is as powerful as clairvoyance. Zbl 1094.68529
Kalyanasundaram, Bala; Pruhs, Kirk
77
2000
A dichotomy theorem for constraint satisfaction problems on a 3-element set. Zbl 1316.68057
Bulatov, Andrei A.
74
2006
Counterexample-guided abstraction refinement for symbolic model checking. Zbl 1325.68145
Clarke, Edmund; Grumberg, Orna; Jha, Somesh; Lu, Yuan; Veith, Helmut
74
2003
The weakest failure detector for solving Consensus. Zbl 0885.68022
Chandra, Tushar Deepak; Hadzilacos, Vassos; Toueg, Sam
73
1996
On the online bin packing problem. Zbl 1326.68337
Seiden, Steven S.
72
2002
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.
71
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
70
1997
Simplify: a theorem prover for program checking. Zbl 1323.68462
Detlefs, David; Nelson, Greg; Saxe, James B.
68
2005
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 clusterings: good, bad and spectral. Zbl 1192.05160
Kannan, Ravi; Vempala, Santosh; Vetta, Adrian
63
2004
Scale-sensitive dimensions, uniform convergence, and learnability. Zbl 0891.68086
Alon, Noga; Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David
63
1997
The complexity of homomorphism and constraint satisfaction problems seen from the other side. Zbl 1312.68101
Grohe, Martin
62
2007
Truth revelation in approximately efficient combinatorial auctions. Zbl 1326.91011
Lehmann, Daniel; O’Callaghan, Liadan Ita; Shoham, Yoav
62
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
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
61
2009
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
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
59
1996
On the (im)possibility of obfuscating programs. Zbl 1281.68118
Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke
59
2012
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
59
2004
Adding nesting structure to words. Zbl 1325.68138
Alur, Rajeev; Madhusudan, P.
59
2009
When are elections with few candidates hard to manipulate? Zbl 1292.91062
Conitzer, Vincent; Sandholm, Tuomas; Lang, Jérôme
56
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.
56
1997
A simple min-cut algorithm. Zbl 0891.68071
Stoer, Mechthild; Wagner, Frank
56
1997
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
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
54
2007
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
54
1998
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
54
2001
The PCP theorem by gap amplification. Zbl 1292.68074
Dinur, Irit
53
2007
All pairs shortest paths using bridging sets and rectangular matrix multiplication. Zbl 1326.05157
Zwick, Uri
53
2002
A new approach to the minimum cut problem. Zbl 0882.68103
Karger, David R.; Stein, Clifford
51
1996
Expander flows, geometric embeddings and graph partitioning. Zbl 1325.68255
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh
51
2009
Efficient noise-tolerant learning from statistical queries. Zbl 1065.68605
Kearns, Michael
49
1998
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
49
2013
Approximating extent measures of points. Zbl 1204.68240
Agarwal, Pankaj K.; Har-Peled, Sariel; Varadarajan, Kasturi R.
48
2004
A theory of goal-oriented communication. Zbl 1281.94004
Goldreich, Oded; Juba, Brendan; Sudan, Madhu
48
2012
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Zbl 1327.68331
Avron, Haim; Toledo, Sivan
46
2011
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 modal analysis of staged computation. Zbl 1323.68107
Davies, Rowan; Pfenning, Frank
46
2001
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
44
1999
Software protection and simulation on oblivious RAMs. Zbl 0885.68041
Goldreich, Oded; Ostrovsky, Rafail
44
1996
Number-theoretic constructions of efficient pseudo-random functions. Zbl 1248.94086
Naor, Moni; Reingold, Omer
44
2004
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
44
2004
A differential approach to inference in Bayesian networks. Zbl 1325.68226
Darwiche, Adnan
44
2003
Noise-tolerant learning, the parity problem, and the statistical query model. Zbl 1325.68114
Blum, Avrim; Kalai, Adam; Wasserman, Hal
44
2003
An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
43
2005
Learning without concentration. Zbl 1333.68232
Mendelson, Shahar
43
2015
A needed narrowing strategy. Zbl 1327.68141
Antoy, Sergio; Echahed, Rachid; Hanus, Michael
42
2000
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Zbl 1321.68274
Dell, Holger; Van Melkebeek, Dieter
42
2014
Convex quadratic and semidefinite programming relaxations in scheduling. Zbl 1323.90024
Skutella, Martin
42
2001
On the impact of combinatorial structure on congestion games. Zbl 1325.91010
Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold
42
2008
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
41
2000
Constraint satisfaction problems solvable by local consistency methods. Zbl 1295.68126
Barto, Libor; Kozik, Marcin
41
2014
Deciding first-order properties of locally tree-decomposable structures. Zbl 1323.03014
Frick, Markus; Grohe, Martin
41
2001
Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields. Zbl 1326.68336
Kleinberg, Jon; Tardos, Éva
41
2002
Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Zbl 1323.68572
Kaplan, Haim; Lewenstein, Moshe; Shafrir, Nira; Sviridenko, Maxim
40
2005
Sampling from large matrices: an approach through geometric functional analysis. Zbl 1326.68333
Rudelson, Mark; Vershynin, Roman
40
2007
Planar graphs have bounded queue-number. Zbl 1466.05047
Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R.
5
2020
Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Zbl 07273073
Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola
3
2020
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 07273087
Kratsch, Stefan; Wahlström, Magnus
3
2020
A simple and approximately optimal mechanism for an additive buyer. Zbl 07273095
Babaioff, Moshe; Immorlica, Nicole; Lucier, Brendan; Weinberg, S. Matthew
3
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
A proof of the CSP dichotomy conjecture. Zbl 07273097
Zhuk, Dmitriy
2
2020
Detecting an odd hole. Zbl 07273076
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie
1
2020
Differential equation invariance axiomatization. Zbl 07273077
Platzer, André; Tan, Yong Kiam
1
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
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
Computing the homology of basic semialgebraic sets in weak exponential time. Zbl 1426.14016
Bürgisser, Peter; Cucker, Felipe; Lairez, Pierre
3
2019
Pseudorandomness from shrinkage. Zbl 1427.68096
Impagliazzo, Russell; Meka, Raghu; Zuckerman, David
3
2019
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
3
2019
The salesman’s improved paths through forests. Zbl 07165880
Sebő, András; Zuylen, Anke Van
3
2019
The Moser-Tardos framework with partial resampling. Zbl 07165888
Harris, David G.; Srinivasan, Aravind
3
2019
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
2
2019
Approaching 3/2 for the \(s\)-\(t\)-path TSP. Zbl 1427.90246
Traub, Vera; Vygen, Jens
2
2019
Shellability is NP-complete. Zbl 07165873
Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
2
2019
Infinite-duration bidding games. Zbl 1448.91060
Avni, Guy; Henzinger, Thomas A.; Chonev, Ventsislav
2
2019
On the parameterized complexity of approximating dominating set. Zbl 07165885
S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin
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
The Weisfeiler-Leman dimension of planar graphs is at most 3. Zbl 07165896
Kiefer, Sandra; Ponomarenko, Ilia; Schweitzer, Pascal
2
2019
Fast learning requires good memory: a time-space lower bound for parity learning. Zbl 1426.68240
Raz, Ran
1
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
Going higher in first-order quantifier alternation hierarchies on words. Zbl 1427.03050
Place, Thomas; Zeitoun, Marc
1
2019
Parallel Bayesian search with no coordination. Zbl 1427.68359
Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav
1
2019
On the computability of conditional probability. Zbl 07165875
Ackerman, Nathanael L.; Freer, Cameron E.; Roy, Daniel M.
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
Non-malleable codes. Zbl 1409.94869
Dziembowski, Stefan; Pietrzak, Krzysztof; Wichs, Daniel
13
2018
Fair enough: guaranteeing approximate maximin shares. Zbl 1410.91314
Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
12
2018
Subcubic equivalences between path, matrix, and triangle problems. Zbl 1426.68133
Williams, Virginia Vassilevska; Williams, R. Ryan
12
2018
Indistinguishability obfuscation from functional encryption. Zbl 1407.94087
Bitansky, Nir; Vaikuntanathan, Vinod
12
2018
Bandits with knapsacks. Zbl 1425.68340
Badanidiyuru, Ashwinkumar; Kleinberg, Robert; Slivkins, Aleksandrs
9
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
Spectral properties of hypergraph Laplacian and approximation algorithms. Zbl 1426.05163
Chan, T.-H. Hubert; Louis, Anand; Tang, Zhihao Gavin; Zhang, Chenzi
5
2018
Matroid secretary problems. Zbl 1425.68461
Babaioff, Moshe; Immorlica, Nicole; Kempe, David; Kleinberg, Robert
5
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
4
2018
Full abstraction for probabilistic PCF. Zbl 1426.68035
Ehrhard, Thomas; Pagani, Michele; Tasson, Christine
4
2018
The parameterized complexity of the \(k\)-biclique problem. Zbl 1426.68131
Lin, Bingkai
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
The applied pi calculus, mobile values, new names, and secure communication. Zbl 1426.68037
Abadi, Martín; Blanchet, Bruno; Fournet, Cédric
2
2018
Proving the incompatibility of efficiency and strategyproofness via SMT solving. Zbl 1425.68385
Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian
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
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
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
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
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
Analysing snapshot isolation. Zbl 1425.68094
Cerone, Andrea; Gotsman, Alexey
1
2018
Rumor spreading and conductance. Zbl 1426.68022
Chierichetti, Flavio; Giakkoupis, George; Lattanzi, Silvio; Panconesi, Alessandro
1
2018
Minimization of tree patterns. Zbl 1426.68076
Czerwiński, Wojciech; Martens, Wim; Niewerth, Matthias; Parys, Paweł
1
2018
Weakest precondition reasoning for expected runtimes of randomized algorithms. Zbl 1426.68298
Kaminski, Benjamin Lucien; Katoen, Joost-Pieter; Matheja, Christoph; Olmedo, Federico
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
Reachability is in DynFO. Zbl 1426.68107
Datta, Samir; Kulkarni, Raghav; Mukherjee, Anish; Schwentick, Thomas; Zeume, Thomas
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
14
2017
Deciding first-order properties of nowhere dense graphs. Zbl 1426.68172
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian
12
2017
Faster polynomial multiplication over finite fields. Zbl 1426.68310
Harvey, David; Van Der Hoeven, Joris; Lecerf, Grégoire
10
2017
Low-rank approximation and regression in input sparsity time. Zbl 1426.65057
Clarkson, Kenneth L.; Woodruff, David P.
10
2017
The 4/3 additive spanner exponent is tight. Zbl 1410.68263
Abboud, Amir; Bodwin, Greg
8
2017
Communication steps for parallel query processing. Zbl 1426.68074
Beame, Paul; Koutris, Paraschos; Suciu, Dan
8
2017
Near-optimal regret bounds for Thompson sampling. Zbl 1426.68293
Agrawal, Shipra; Goyal, Navin
7
2017
On the switch Markov chain for perfect matchings. Zbl 1426.60097
Dyer, Martin; Jerrum, Mark; Müller, Haiko
6
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
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
Separations in query complexity based on pointer functions. Zbl 1426.68109
Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris
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
Homotopy-initial algebras in type theory. Zbl 1426.03016
Awodey, Steve; Gambino, Nicola; Sojakova, Kristina
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
Parallel-correctness and transferability for conjunctive queries. Zbl 1426.68073
Ameloot, Tom J.; Geck, Gaetano; Ketsman, Bas; Neven, Frank; Schwentick, Thomas
2
2017
Estimating the unseen, improved estimators for entropy and other properties. Zbl 1426.62107
Valiant, Gregory; Valiant, Paul
2
2017
Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length. Zbl 1426.68088
Bournez, Olivier; Graça, Daniel S.; Pouly, Amaury
2
2017
The power of localization for efficiently learning linear separators with noise. Zbl 1426.68234
Awasthi, Pranjal; Balcan, Maria Florina; Long, Philip M.
2
2017
A temporal logic approach to binding-time analysis. Zbl 1426.68034
Davies, Rowan
2
2017
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2017
Reconciliation with nonbinary gene trees revisited. Zbl 1426.92050
Zheng, Yu; Zhang, Louxin
1
2017
Source sets: a foundation for optimal dynamic partial order reduction. Zbl 1426.68038
Abdulla, Parosh Aziz; Aronis, Stavros; Jonsson, Bengt; Sagonas, Konstantinos
1
2017
...and 650 more Documents
all top 5

Cited by 14,484 Authors

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

Cited in 580 Journals

1,151 Theoretical Computer Science
524 Algorithmica
383 Journal of Computer and System Sciences
294 Information and Computation
293 SIAM Journal on Computing
286 Information Processing Letters
284 Discrete Applied Mathematics
240 Theory of Computing Systems
216 Artificial Intelligence
191 Distributed Computing
165 Journal of Combinatorial Optimization
134 Mathematical Programming. Series A. Series B
111 SIAM Journal on Discrete Mathematics
107 Computational Complexity
104 European Journal of Operational Research
102 Journal of Discrete Algorithms
98 Journal of Cryptology
90 Discrete & Computational Geometry
90 Computational Geometry
88 Operations Research Letters
81 Information Sciences
77 Annals of Mathematics and Artificial Intelligence
69 Journal of Automated Reasoning
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 International Journal of Foundations of Computer Science
58 Acta Informatica
57 Discrete Mathematics
57 Random Structures & Algorithms
57 Logical Methods in Computer Science
56 Games and Economic Behavior
55 Discrete Optimization
52 Computers & Operations Research
51 Linear Algebra and its Applications
46 International Journal of Approximate Reasoning
45 International Journal of Theoretical Physics
45 Operations Research
44 Machine Learning
43 The Annals of Statistics
43 European Journal of Combinatorics
42 International Journal of Computational Geometry & Applications
42 Journal of Scheduling
42 Journal of Machine Learning Research (JMLR)
39 Annals of Operations Research
39 Foundations of Computational Mathematics
38 SIAM Journal on Matrix Analysis and Applications
38 Journal of Logical and Algebraic Methods in Programming
37 Formal Aspects of Computing
36 Journal of Complexity
36 MSCS. Mathematical Structures in Computer Science
34 Journal of the ACM
34 ACM Transactions on Computational Logic
34 Computer Science Review
33 Journal of Parallel and Distributed Computing
33 Designs, Codes and Cryptography
33 Combinatorics, Probability and Computing
32 Journal of Global Optimization
31 Optimization Letters
30 Neural Computation
30 Computational Optimization and Applications
30 SIAM Journal on Scientific Computing
28 Constraints
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
26 Journal of Computational and Applied Mathematics
25 International Journal of Computer Vision
24 Combinatorica
24 Annals of Pure and Applied Logic
24 Applied and Computational Harmonic Analysis
24 Journal of Applied Logic
23 SIAM Journal on Optimization
22 Applied Mathematics and Computation
22 Automatica
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 International Journal of Quantum Information
18 Electronic Journal of Statistics
17 Computing
17 Studia Logica
17 Journal of Mathematical Imaging and Vision
17 Journal of Applied Non-Classical Logics
17 Journal of Graph Algorithms and Applications
16 Advances in Mathematics
16 The Annals of Applied Probability
16 International Journal of Computer Mathematics
16 INFORMS Journal on Computing
15 Computers & Mathematics with Applications
15 Communications in Mathematical Physics
15 Journal of Mathematical Physics
...and 480 more Journals
all top 5

Cited in 62 Fields

7,791 Computer science (68-XX)
2,253 Operations research, mathematical programming (90-XX)
2,012 Combinatorics (05-XX)
1,038 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
935 Information and communication theory, circuits (94-XX)
880 Mathematical logic and foundations (03-XX)
611 Numerical analysis (65-XX)
501 Statistics (62-XX)
350 Quantum theory (81-XX)
340 Probability theory and stochastic processes (60-XX)
310 Linear and multilinear algebra; matrix theory (15-XX)
237 Biology and other natural sciences (92-XX)
177 Convex and discrete geometry (52-XX)
120 Number theory (11-XX)
95 Algebraic geometry (14-XX)
91 Systems theory; control (93-XX)
84 Order, lattices, ordered algebraic structures (06-XX)
71 Statistical mechanics, structure of matter (82-XX)
64 General algebraic systems (08-XX)
64 Group theory and generalizations (20-XX)
61 Commutative algebra (13-XX)
60 Functional analysis (46-XX)
59 Calculus of variations and optimal control; optimization (49-XX)
57 Manifolds and cell complexes (57-XX)
49 Partial differential equations (35-XX)
38 Field theory and polynomials (12-XX)
38 Algebraic topology (55-XX)
37 Dynamical systems and ergodic theory (37-XX)
37 Geometry (51-XX)
29 Approximations and expansions (41-XX)
29 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)
19 General and overarching topics; collections (00-XX)
18 Fluid mechanics (76-XX)
17 Functions of a complex variable (30-XX)
16 Associative rings and algebras (16-XX)
16 Ordinary differential equations (34-XX)
13 Real functions (26-XX)
13 Measure and integration (28-XX)
12 Global analysis, analysis on manifolds (58-XX)
12 Mechanics of deformable solids (74-XX)
12 Geophysics (86-XX)
10 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 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 Abstract harmonic analysis (43-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