: www.idealibrary.com on The Space Complexity of Approximating the Frequency Moments* (2008)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing mi elements of type i, 1 i n, are the numbers Fk = n i=1 m k i. We consider the space complexity of randomized algorithms that approximate the numbers...
The quantum adversary method and (2008)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
Languages with Bounded Multiparty Communication Complexity ∗ (2008)
Arkadev Chattopadhyay, Pascal Tesson, Andreas Krebs, Mario Szegedy, Denis Thérien
grateful to Pavel Pudlák for suggesting the use of the Hales-Jewett Theorem. We study languages with bounded communication complexity in the multiparty “input on the forehead model ” with...
Abstract Tracking Join and Self-Join Sizes in Limited Storage (2008)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
gibbonsOresearch.bell-labs.com Query optimizers rely on fast, high-quality estimates of re-sult sizes in order to select between various join plans. Self-join sizes of relations provide bounds on the...
Noga Alon, Yossi Matias, Mario Szegedy
space complexity of approximating the frequency moments
Languages with Bounded Multiparty Communication Complexity ∗ (2008)
Arkadev Chattopadhyay, Pascal Tesson, Andreas Krebs, Mario Szegedy, Denis Thérien
for suggesting the use of the Hales-Jewett Theorem. Academy of Sciences Czech Republic We study languages with bounded communication complexity in the multiparty “input on the forehead model ”...
Abstract Quantum Algorithms for the Triangle Problem (2008)
Frédéric Magniez, Miklos Santha, Mario Szegedy
We present two new quantum algorithms that either find a triangle (a copy of K3) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas...
A Clique Size Bounding Technique with Application to Non-Linear Codes (2008)
Introduction We introduce a method to give upper estimates for the clique size of intermediately large graphs. The method can be applied when the graph in question is symmetrical to a large degree....
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
We show that every language in NP has a probablistic verier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a...
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...
On the variance of subset sum estimation (2007)
Szegedy, Mario, Thorup, Mikkel
For high volume data streams and large data warehouses, sampling is used for efficient approximate answers to aggregate queries over selected subsets. Mathematically, we are dealing with a set of...
ABSTRACT OF THE DISSERTATION Quantum walks and ground state problems (2007)
Courtland Richter, Mario Szegedy, Peter Courtland Richter, Dissertation Director, Mario Szegedy
Since the appearance of Shor’s factoring algorithm in 1994, the search for novel quantum computer algorithms has proved surprisingly difficult. Two design approaches that have yielded some progress...
ABSTRACT OF THE DISSERTATION Some Problems in Discrete Geometry (2006)
Mario Szegedy, Xiaomin Chen, Dissertation Director, Mario Szegedy
The Sylvester-Gallai theorem asserts that any non-collinear point set in the plane de-termines a line passing through exactly two points in the set. The problem was posed by Sylvester in 1893 and...
The quantum adversary method and classical formula size lower bounds (2005)
Laplante, Sophie, Lee, Troy, Szegedy, Mario
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has been emerging...
Quantum algorithms for the triangle problem (2005)
Fr Édéric Magniez, Miklos Santha, Mario Szegedy
Abstract. We present two new quantum algorithms that either find a triangle (a copy of K3) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial...
The quantum adversary method and (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
The quantum adversary method and (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
Quantum algorithms for the triangle problem (2005)
Fr Édéric Magniez, Miklos Santha, Mario Szegedy
Abstract. We present two new quantum algorithms that either find a triangle (a copy of K3) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial...
All quantum adversary methods are equivalent (2005)
Robert ˇ Spalek, Mario Szegedy
Abstract. The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equal: spectral adversary [1],...
All Quantum Adversary Methods are Equivalent (2004)
Spalek, Robert, Szegedy, Mario
The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equivalent: spectral adversary (Barnum, Saks,...
Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule (2004)
We introduce quantized bipartite walks, compute their spectra, generalize the algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as quantum walks with memory. We compare the...
Quantum and classical query complexities of local search are polynomially related (2004)
Let f be an integer valued function on a finite set V. We call an undirected graph G(V, E) a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed...
Quantum Algorithms for the Triangle Problem (2003)
Magniez, Frederic, Santha, Miklos, Szegedy, Mario
We present two new quantum algorithms that either find a triangle (a copy of $K_{3}$) in an undirected graph $G$ on $n$ nodes, or reject if $G$ is triangle free. The first algorithm uses...
On the Quantum Query Complexity of Detecting Triangles in Graphs (2003)
We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on $n$ nodes can be done using $O(n^{1+{3\over 7}}\log^{2}n)$ quantum queries. The same...
Long monotone paths in line arrangements (2003)
Oded Regev, William Steiger, Mario Szegedy
We show how to construct an arrangement of n lines having a monotone path of length n
Long monotone paths in line arrangements (2003)
József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
() N — = #+V ( * () =8-H S () = ()žŸŽi ’=;¡2 ’ ¢ ” £[ ¤ ¥ – œSH( *!Y
Tracking Join and Self-Join Sizes in Limited Storage (2002)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
This paper presents algorithms for tracking (approximate) join and self-join sizes in limited storage, in the presence of insertions and deletions to the data set(s). Such algorithms detect changes...
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a, b ∈ C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi ∈ {ai, bi} for all 1...
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a; b 2 C, let D(a; b) be the set of all descendants of a and b, that is, all words x of length 4 where x i 2 fa i; b i g for all 1...
On-line complexity of Monotone Set Systems (1999)
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a 1: : : a r. In this paper a 1; : : : ; a r are...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Just the Fax-Differentiating Voice and Fax Phone Lines Using Call Billing Data (1999)
Haim Kaplan, Martin Strauss, Mario Szegedy
this paper we are particularly concerned with classifying lines as either voice or fax, we point out that the techniques we use may apply in other classification problems as well. The ability to...
On-line Complexity of Monotone Set Systems (1999)
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a1 : : : ar . In this paper a1 ; : : : ; ar are...
how many steps the k peg version of the Towers of Hanoi Game can be solved (1999)
Abstract. In this we paper we consider the version of the classical Towers of Hanoi games where the game-board contains more than three pegs. For k pegs we give a 2 Ckn 1/(k−2) lower bound on the...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ɛ-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Algorithms to Tile the Infinite Grid with Finite Clusters (1998)
Mario Szegedy, Tiles Z, Tiles Z
We say that a subset T of Z 2 , the two dimensional infinite grid, tiles Z 2 if we can cover Z 2 with non-overlapping translates of T . No algorithm is known to decide whether a finite T ` Z 2 tiles...
Exponential Lower Bounds for the Towers of Hanoi with More Than Three Pegs (1998)
In this we paper we consider the version of the classical Towers of Hanoi games where the gameboard contains more than three pegs. For k pegs we give a 2 C k n 1=k\Gamma2 lower bound on the number of...
On-line Complexity of Monotone Set Systems (1998)
On-line models assume a player, A (randomized or deterministic), who makes immediate responses to incomming elements of an input sequence s = a 1 : : : a r . In this paper we study the case, when the...
The space complexity of approximating the frequency moments (1996)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing mi elements of type i, for 1 ≤ i ≤ n, are the numbers Fk = �n i=1 mki. We consider the space complexity of randomized algorithms that approximate...
Interactive proofs and the hardness of approximating cliques (1996)
Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy
The contribution of this paper is two-fold. First, a connection is shown between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient...
Public vs. Private coin flips in one round communication games (Extended Abstract) (1996)
) Ilan Newman and Mario Szegedy y Abstract We study 1-round two parties communication complexity games, where private random bits are used. We observe that the existence of good protocols for such...
The Space Complexity of Approximating the Frequency Moments (1996)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing m i elements of type i, for 1 i n, are the numbers Fk = P n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the...
On conway’s thrackle conjecture (1995)
László Lovász, János Pach, Mario Szegedy
A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to...
Interactive Proofs and the Hardness of Approximating Cliques (1995)
Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy
The contribution of this paper is two-fold. First, a connection is shown between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient...
Fault Tolerant Circuits and Probabilistically Checkable Proofs (1995)
We introduce a new model of fault tolerant Boolean circuits. We allow an adversary to choose some gates to be faulty, unlike the model considered by von Neumann and Pippenger where the errors are...
Fault Tolerant Circuits and Probabilistically Checkable Proofs (1995)
We introduce a new model of fault tolerance for Boolean circuits. We consider synchronized circuits and we allow an adversary to choose a small constant fraction of the gates at each level of the...
Lower Bounds for On-line Graph Coloring Magn'us M. Halld'orsson \Lambda (1994)
Abstract An algorithm for vertex-coloring graphs is said to be on-line if each vertex is irrevocably assigned a color before later vertices are considered. We show that for every such algorithm,...
Fault Tolerant Circuits and Probabilistically Checkable Proofs (1993)
We introduce a new model of fault tolerance for Boolean circuits. We consider synchronized circuits and we allow an adversary to choose a small constant fraction of the gates at each level of the...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If...
On the Degree of Boolean Functions as Real Polynomials (1992)
Noam Nisan Mario, Mario Szegedy
Every boolean function may be represented as a real polynomial. In this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function. Our...
On the Power of Two-Local Random Reductions (1992)
We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP/poly"co-NP/poly. This extends and simplifies a result by Yao. 1 Introduction...
Proof Verification and Hardness of Approximation Problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If...
Checking Computations in Polylogarithmic Time (1991)
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof...
Efficient Testing of Large Graphs
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...