Testing for Concise Representations

No abstract is available for this paper.

• Publication year

  2007

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2007-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2007.32
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An improved approximation ratio for the minimum linear arrangement problem

  2007cited by this paper
• Scheduling with Precedence Constraints of Low Fractional Dimension

  2007cited by this paper
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring

  2006cited by this paper
• Integrality gaps for sparsest cut and minimum linear arrangement problems

  2006cited by this paper
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

  2006cited by this paper
• ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

  2005cited by this paper
• New Approximation Techniques for Some Linear Ordering Problems

  2005cited by this paper
• Single-Machine Scheduling with Precedence Constraints

  2005cited by this paper
• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

  2005cited by this paper
• Testing polynomials over general fields

  2004cited by this paper
• A lower bound for testing juntas

  2004cited by this paper
• Testing low-degree polynomials over prime fields

  2004cited by this paper
• Inapproximability of Combinatorial Optimization Problems

  2004cited by this paper
• Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

  2004influential reference
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time

  2003cited by this paper
• Testing Low-Degree Polynomials over GF(2(

  2003cited by this paper
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

  2003cited by this paper
• Testing Basic Boolean Formulae

  2002influential reference
• Relations between average case complexity and approximation complexity

  2002cited by this paper
• Testing Problems with Sublearning Sample Complexity

  2000cited by this paper
• Polynomial time approximation algorithms for machine scheduling: ten open problems

  1999cited by this paper
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

  1999cited by this paper
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine

  1999influential reference
• Fourier Analysis on Finite Groups and Applications: Finite Symmetric Spaces–Finite Upper Half Plane H q

  1999cited by this paper
• Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine

  1999cited by this paper
• Testing problems with sub-learning sample complexity

  1998cited by this paper
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

  1997cited by this paper
• Scheduling to minimize average completion time: offline and online algorithms

  1997cited by this paper
• Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds

  1996cited by this paper
• Scheduling to minimize average completion time: off-line and on-line algorithms

  1996cited by this paper
• Property testing and its connection to learning and approximation

  1996cited by this paper
• On the degree of boolean functions as real polynomials

  1992cited by this paper
• Combinatorics and Partially Ordered Sets: Dimension Theory

  1992cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Learning DNF under the uniform distribution in quasi-polynomial time

  1990cited by this paper
• Group representations in probability and statistics

  1988influential reference
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

  1978cited by this paper
• Probabilistic computations: Toward a unified measure of complexity

  1977cited by this paper
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

  1977cited by this paper
• and as an in

  year unknowninfluential reference

• Strong Pseudorandom Functions in AC0[2] in the Bounded-Query Setting

  2025cites this paper
• Relative-error testing of conjunctions and decision lists

  2025influential citation
• Let's Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk)

  2025cites this paper
• Polynomial-Time Tolerant Testing Stabilizer States

  2024cites this paper
• Testing Sumsets is Hard

  2024cites this paper
• Tolerant Quantum Junta Testing

  2024cites this paper
• Relative-error monotonicity testing

  2024cites this paper
• Testing Self-Reducible Samplers

  2023cites this paper
• (Quantum) complexity of testing signed graph clusterability

  2023cites this paper
• Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

  2023cites this paper
• A strong composition theorem for junta complexity and the boosting of property testers

  2023cites this paper
• Almost Optimal Proper Learning and Testing Polynomials

  2022cites this paper
• On Testing Decision Tree

  2022cites this paper
• Testing of Index-Invariant Properties in the Huge Object Model

  2022cites this paper
• Sparsification for Sums of Exponentials and its Algorithmic Applications

  2021cites this paper
• Junta distance approximation with sub-exponential queries

  2021cites this paper
• Robust Model Selection and Nearly-Proper Learning for GMMs

  2021cites this paper
• Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

  2021cites this paper
• On Learning and Testing Decision Tree

  2021cites this paper
• How Close is your Function to Depending on a Small Number of its Inputs?

  2021cites this paper
• Reconstruction and testing via decision trees

  2021cites this paper
• BIROn - Birkbeck Institutional Research Online and extending the

  2020cites this paper
• An Optimal Tester for $k$-Linear

  2020cites this paper
• SoK: A Consensus Taxonomy in the Blockchain Era

  2020cites this paper
• How to Extract Useful Randomness from Unreliable Sources

  2020cites this paper
• Robust testing of low dimensional functions

  2020cites this paper
• Testing and reconstruction via decision trees

  2020cites this paper
• Active Local Learning

  2020cites this paper
• Reconstructing Decision Trees

  2020cites this paper
• Junta Correlation is Testable

  2019cites this paper
• J an 2 01 9 Almost Optimal Distribution-free Junta Testing

  2019cites this paper
• Almost Optimal Testers for Concise Representations

  2019influential citation
• Near-Optimal Algorithm for Distribution-Free Junta Testing

  2019cites this paper
• Adaptively Secure MPC with Sublinear Communication Complexity

  2019cites this paper
• Almost optimal distribution-free junta testing

  2019cites this paper
• Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits

  2018cites this paper
• Distribution-free junta testing

  2018cites this paper
• Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications

  2018cites this paper
• Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

  2018cites this paper
• Public-Key Encryption Resistant to Parameter Subversion and its Realization from Efficiently-Embeddable Groups

  2018cites this paper
• Constant Round Adaptively Secure Protocols in the Tamper-Proof Hardware Model

  2017cites this paper
• Introduction to Property Testing

  2017influential citation
• A Unified Approach to Constructing Black-Box UC Protocols in Trusted Setup Models

  2017cites this paper
• Concurrently Composable Security with Shielded Super-Polynomial Simulators

  2017cites this paper
• Settling the Query Complexity of Non-adaptive Junta Testing

  2017cites this paper
• Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms

  2016cites this paper
• Improving and Extending the Testing of Distributions for Shape-Restricted Properties

  2016cites this paper
• Lecture Notes on Testing by Implicit Sampling

  2016influential citation
• On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

  2016cites this paper
• A characterization of constant‐sample testable properties

  2016cites this paper
• Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

  2016cites this paper
• Testing Submodularity and Other Properties of Valuation Functions

  2016cites this paper
• NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion

  2016cites this paper
• Analysis of Algebraic complexity classes and boolean functions [HBNI Th106]

  2016cites this paper
• On Black-Box Complexity of Universally Composable Security in the CRS Model

  2015cites this paper
• Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs

  2015cites this paper
• PARTIALLY SYMMETRIC FUNCTIONS ARE EFFICIENTLY

  2015cites this paper
• Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

  2015cites this paper
• Adaptivity Helps for Testing Juntas

  2015cites this paper
• Learning and testing junta distributions over hypercubes

  2015cites this paper
• Learning Sparse Polynomial Functions

  2014cites this paper
• Lp-testing

  2014cites this paper
• A characterization of locally testable affine-invariant properties via decomposition theorems

  2014influential citation
• Minimum Linear Arrangement of Series-Parallel Graphs

  2014cites this paper
• (Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens

  2014cites this paper
• Polynomial Decompositions in Polynomial Time

  2014cites this paper
• Cross-Domain Secure Computation

  2014cites this paper
• Online Privacy: Towards Informational Self-Determination on the Internet

  2013cites this paper
• Mathematical Theories of Interaction with Oracles

  2013cites this paper
• Feasibility and Completeness of Cryptographic Tasks in the Quantum World

  2013cites this paper
• Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

  2013cites this paper
• Testing Linear-Invariant Function Isomorphism

  2013cites this paper
• Adaptive and Concurrent Secure Computation from New Adaptive, Non-malleable Commitments

  2013cites this paper
• Distance-Sensitive Property Testing Lower Bounds

  2013cites this paper
• A Tight Lower Bound for Monotonicity Testing over Large Ranges

  2013cites this paper
• Query-efficient computation in property testing and learning theory

  2012cites this paper
• Tight Bounds for Testing k-Linearity

  2012cites this paper
• Impossibility Results for Static Input Secure Computation

  2012cites this paper
• Universal Composability from Essentially Any Trusted Setup

  2012cites this paper
• Black-Box Constructions of Composable Protocols without Set-Up

  2012cites this paper
• Lower Bounds on Testing Functions of Low Fourier Degree

  2012cites this paper
• Testing Properties of Linear Functions

  2012cites this paper
• Testing k-wise independent distributions

  2012cites this paper
• New Impossibility Results for Concurrent Composition and a Non-Interactive Completeness Theorem for Secure Computation

  2012cites this paper
• Testing properties of boolean functions

  2012influential citation
• Fast Approximation Algorithms for Graph Partitioning Using Spectral and Semidefinite-Programming Techniques

  2011cites this paper
• Active Property Testing

  2011cites this paper
• Algebraic Property Testing

  2011cites this paper
• Framework for Testing Linear-Invariant Properties

  2011cites this paper
• Testing Properties of Boolean Functions : Lower Bounds on Testing Fourier Degree

  2011cites this paper
• Distribution-Free Testing of Monomials with a Sublinear Number of Queries

  2011cites this paper
• Nearly tight bounds for testing function isomorphism

  2011influential citation
• The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem

  2011cites this paper
• Distribution-Free Testing for Monomials with a Sublinear Number of Queries

  2011cites this paper
• Active Testing

  2011cites this paper
• Testability of linear-invariant properties

  2011cites this paper
• Partially Symmetric Functions Are Efficiently Isomorphism-Testable

  2011cites this paper
• Invariance in Property Testing

  2010cites this paper
• Property testing on boolean functions Thesis proposal

  2010cites this paper
• Computational systems biology

  2010cites this paper