Arrow Research search

Author name cluster

Jared Saia

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

TCS Journal 2024 Journal Article

Boundary sketching with asymptotically optimal distance and rotation

  • Varsha Dani
  • Abir Islam
  • Jared Saia

We address the problem of designing a distributed algorithm for two robots that sketches the boundary of an unknown shape. Critically, we assume a certain amount of delay in how quickly our robots can react to external feedback. In particular, when a robot moves, it commits to move along path of length at least λ, or turn an amount of radians at least λ for some positive λ ≤ 1 / 2 6, that is normalized based on a unit diameter shape. Then, our algorithm outputs a polygon that is an ϵ-sketch, for ϵ = 8 λ, in the sense that every point on the shape boundary is within distance ϵ of the output polygon. Moreover, our costs are asymptotically optimal in two key criteria for the robots: total distance traveled and total amount of rotation. Additionally, we implement our algorithm, and illustrate its output on some specific shapes.

Details DOI

TCS Journal 2024 Journal Article

Defending hash tables from algorithmic complexity attacks with resource burning

  • Trisha Chakraborty
  • Jared Saia
  • Maxwell Young

We consider the problem of defending a hash table against a Byzantine attacker that is trying to degrade the performance of query, insertion and deletion operations. Our defense makes use of resource burning (RB)—the verifiable expenditure of network resources—where the issuer of a request incurs some RB cost. Our algorithm, Depth Charge, charges RB costs for operations based on the depth of the appropriate object in the list that the object hashes to in the table. By appropriately setting the RB costs, our algorithm mitigates the impact of an attacker on the hash table's performance. In particular, in the presence of a significant attack, our algorithm incurs a cost which is asymptotically less that the attacker's cost.

Details DOI

I&C Journal 2018 Journal Article

Interactive communication with unknown noise rate

  • Varsha Dani
  • Thomas P. Hayes
  • Mahnush Movahedi
  • Jared Saia
  • Maxwell Young

Alice and Bob want to run a protocol over a noisy channel, where some bits are flipped adversarially. Several results show how to make an L-bit noise-free communication protocol robust over such a channel. In a recent breakthrough, Haeupler described an algorithm sending a number of bits that is conjecturally near optimal for this model. However, his algorithm critically requires prior knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge, under the additional assumption that the channel connecting Alice and Bob is private. If an adversary flips T bits, our algorithm sends L + O ( L ( T + 1 ) log ⁡ L + T ) bits in expectation and succeeds with high probability in L. It does so without any a priori knowledge of T. Assuming a lower bound conjectured by Haeupler, our result is optimal up to logarithmic factors.

Details DOI

STOC Conference 2013 Conference Paper

Byzantine agreement in polynomial expected time: [extended abstract]

  • Valerie King
  • Jared Saia

In the classic asynchronous Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds; the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm; and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as "strong". We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the first improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm tolerates an adversary that controls up to a $1/500$ fraction of the processors.

Details

FOCS Conference 2006 Conference Paper

Towards Secure and Scalable Computation in Peer-to-Peer Networks

  • Valerie King
  • Jared Saia
  • Vishal Sanwalani
  • Erik Vee

We consider the problems of Byzantine agreement and leader election, where a constant fraction b < 1/3 of processors are controlled by a malicious adversary. The first problem requires that all uncorrupted processors come to an agreement on a bit initially held by one of the uncorrupted processors; the second requires that the uncorrupted processors choose a leader who is uncorrupted. Motivated by the need for robust and scalable computation in peer-to-peer networks, we design the first scalable protocols for these problems for a network whose degree is polylogarithmic in its size. By scalable, we mean that each uncorrupted processor sends and processes a number of bits that is only polylogarithmic in n. (We assume no limit on the number of messages sent by corrupted processors.) With high probability, our Byzantine agreement protocol results in agreement among a 1 - O(1/ln n) fraction of the uncorrupted processors. With constant probability, our leader election protocol elects an uncorrupted leader and ensures that a 1 - O(1/ln n) fraction of the uncorrupt processors know this leader. We assume a full information model. Thus, the adversary is assumed to have unlimited computational power and has access to all communications, but does not have access to processors' private random bits

Details

STOC Conference 2001 Conference Paper

Spectral analysis of data

  • Yossi Azar
  • Amos Fiat
  • Anna R. Karlin
  • Frank McSherry
  • Jared Saia

Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. These results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.

Details
v2026.09.13